<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">


<html>
<head>
	<title>Writing own regular expression parser - CodeProject</title> 
	<link type="text/css" rel="stylesheet" href="http://s.codeproject.com/App_Themes/CodeProject/Css/Main.min.css?dt=2.8.140402.1">

	
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="Description" content="Explains principles behind writing regular expression parsers.; Author: Amer Gerzic; Updated: 15 Nov 2003; Section: Algorithms &amp; Recipes; Chapter: General Programming; Updated: 15 Nov 2003" />
<meta name="Keywords" content="VC6, VC7, VC7.1, Win2K, WinXP, Win2003, STL, Dev, Beginner,Algorithms &amp; Recipes,General Programming,Free source code, tutorials" />
<meta name="Author" content="Amer Gerzic" />
<meta name="Rating" content="General" />
<meta name="Robots" content="index, follow, NOODP" />
<meta name="Revisit-After" content="1 days" />
<meta name="application-name" content="CodeProject" />

<link rel="dns-prefetch" href="//ajax.googleapis.com" /> 
<link rel="canonical" href="/Articles/5412/Writing-own-regular-expression-parser" />


<link rel="alternate" type="application/rss+xml" title="CodeProject Latest articles - All Topics" href="http://www.codeproject.com/WebServices/ArticleRSS.aspx?cat=1" />
<link rel="alternate" type="application/rss+xml" title="CodeProject Latest articles - Android" href="http://www.codeproject.com/WebServices/ArticleRSS.aspx?cat=22" />
<link rel="alternate" type="application/rss+xml" title="CodeProject Latest articles - C++" href="http://www.codeproject.com/WebServices/ArticleRSS.aspx?cat=2" />
<link rel="alternate" type="application/rss+xml" title="CodeProject Latest articles - C#" href="http://www.codeproject.com/WebServices/ArticleRSS.aspx?cat=3" />
<link rel="alternate" type="application/rss+xml" title="CodeProject Latest articles - Web" href="http://www.codeproject.com/WebServices/ArticleRSS.aspx?cat=23" />
<link rel="alternate" type="application/rss+xml" title="CodeProject Latest articles - Mobile" href="http://www.codeproject.com/WebServices/ArticleRSS.aspx?cat=18" />
<link rel="alternate" type="application/rss+xml" title="CodeProject Lounge Postings" href="http://www.codeproject.com/webservices/LoungeRSS.aspx" />
<link rel="search" type="application/opensearchdescription+xml" title="CodeProject" href="http://www.codeproject.com/info/OpenSearch.xml" />

	<base target="_top" />
	<link rel="icon" href="/favicon.ico" type="image/ico" >
<link rel="shortcut icon" href="/favicon.ico"  type="image/ico" >
<link rel="apple-touch-icon" href="/images/FavIcon-Apple.png" type="image/png" >
<script type="text/javascript" language="Javascript">//<![CDATA[
function defrm () { /* thanks twitter */ document.write = ''; window.top.location = window.self.location;  setTimeout(function() { document.body.innerHTML = ''; }, 0);  window.self.onload = function(evt) { document.body.innerHTML = ''; }; }if (window.top !== window.self) {  try {  if (window.top.location.host) { /* will throw */ } else { defrm(); /* chrome */ }  } catch (ex) { defrm(); /* everyone else */ } }if (typeof(DemoUrl)!='undefined')   document.write(unescape('%3Cme')+'ta http'+'-equiv="re'+'fresh"                  con'+'tent="1;url='+DemoUrl+unescape('"%3CE'));
function _dmBootstrap(file) { var _dma = document.createElement('script');  _dma.type = 'text/javascript'; _dma.async = true;  _dma.src = ('https:' == document.location.protocol ? 'https://' : 'http://') + file; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(_dma);}
function _dmFollowup(file) { if (typeof DMAds === 'undefined')  _dmBootstrap('cdn2.developermedia.com/a.min.js?dt=2.8.140402.1');}
(function () { _dmBootstrap('cdn1.developermedia.com/a.min.js?dt=2.8.140402.1'); setTimeout(_dmFollowup, 2000);})();

//]]>
</script>

	




<script type="text/javascript">
	var _gaq = _gaq || [];
	_gaq.push(['_setAccount', 'UA-1735123-1']);
	_gaq.push(['_trackPageview']);
	_gaq.push(['_setDomainName', 'www.codeproject.com']);
	_gaq.push(['_setSessionTimeout', '1200']); 

	(function () {
		var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
		ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
		(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(ga);
	})(); 
</script>


</head>	

<body class="safari safari5">

<a href="#Main"><img alt="Click here to Skip to main content" class="access-link" src="/Images/t.gif" /></a>





<div class="page-background">

	
	

	

	<table id="ctl00_Bn" style="width:100%;height:135px" cellpadding="0" cellspacing="0" class="banner fixed">
	<tr valign="bottom">
		<td class="blank-background" style="height:31px">&nbsp;</td>
		<td class="blank-background" rowspan="3" style="width:250px;height:135px"><a href="/"><img id="ctl00_Logo" tabindex="1" title="CodeProject" src="http://s.codeproject.com/App_Themes/CodeProject/Img/logo250x135.gif" alt="Home" style="height:135px;width:250px;border-width:0px;" /></a></td>
		<td class="blank-background align-right" style="width:728px;height:31px">

<div class="container memberbar clearfix">

	<div id="ctl00_MemberMenu_GenInfo" class="float-left">10,512,171 members (37,668 online) &nbsp; &nbsp; </div>

	<div class="float-left">
		
	</div>

	<div class="float-right">

        <span class="tooltip">
            <a href="http://workspaces.codeproject.com" id="ctl00_MemberMenu_Workspaces"><img 
                src="/images/workspaces32.png" height="16px" width="110px" 
                style="border:0;margin: -2px 25px 0 0;vertical-align:middle" /></a>

            <div class="tooltip-flyout workspaces">

                <h3>CodeProject::Workspaces</h3>
                <p class=bold>Code. Collaborate. Organize.</p>
	                <div class="list-item"><a href="https://workspaces.codeproject.com">Workspaces Home</a></div>
	                <div class="list-item"><a href="http://www.codeproject.com/Forums/1854922/Workspaces-Forum.aspx">Discuss Workspaces</a></div>
                <p style='margin-top:10px' class=bold>No Limits. <a href="https://workspaces.codeproject.com">Try it Today.</a></p>
			</div>

		</span>

		

		

		

			<script type="text/javascript">//<!--
			function doSubmit(secure)
			{
				if (secure)
					document.subForm.action = "https://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser"
				else
					document.subForm.action = "https://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser"
				document.subForm.submit();
				return true;
			}//-->
			</script>

			<a name="SignUp"></a>
			<span class="member-signin tooltip openable">
				<span><a href="https://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign in</a></span>

				<div class="tooltip-flyout">
					<form name="subForm" id="subForm" action="https://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser" method="post" 
						class="tight">

						
						<input id="FormName" name="FormName" value="MenuBarForm" type="hidden" />

						<div>Email</div>
						<div><input class="small-text" type="email" name="Email" id="Email" /></div>
						<div>Password</div>
						<div><input class="small-text" type="password" name="Password" id="Password" /></div>
						<div class="action">
							
<script type="text/javascript">
function Join(){
 var url = 'http://www.codeproject.com/script/Membership/Modify.aspx?meml=' + document.subForm.Email.value;
 document.location.href=url;return false;
}
document.write('<input type="button" class="create"   onclick="return Join();" value="Join"');
document.write('<input type="hidden" name="fld_quicksign"   value="true" />');
</script>
							<input type="submit" value="Sign in" class="signin" 
								onclick="return doSubmit(false);" />
						</div>

						<div class="container">
							
							&nbsp;
							<a id="ctl00_MemberMenu_SendPassword" class="forgot float-right" href="/script/Membership/SendPassword.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Forgot your password?</a>
						</div>
					</form>

					<hr class="divider-dark" />

					Sign in using <a class="oauth" title="Sign in using Facebook" href="/script/Membership/OAuthLogOn.aspx?auth=Facebook"><img src="/script/Membership/Images/facebook.png" style="vertical-align:middle;padding-right:3px;border:0;" /></a>
<a class="oauth" title="Sign in using Google" href="/script/Membership/OAuthLogOn.aspx?auth=Google"><img src="/script/Membership/Images/google-plus.png" style="vertical-align:middle;padding-right:3px;border:0;" /></a>
<a class="oauth" title="Sign in using Linkedin" href="/script/Membership/OAuthLogOn.aspx?auth=LinkedIn"><img src="/script/Membership/Images/linkedin.png" style="vertical-align:middle;padding-right:3px;border:0;" /></a>

				</div>
		
	</div>
</div></td>
		<td class="blank-background" style="height:31px">&nbsp;</td>
	</tr>
	<tr valign="middle">
		<td class="theme1-background" style="height:94px">&nbsp;</td>
		<td class="theme1-background ad"><div class="msg-728x90" data-format="728x90" data-type="ad" data-publisher="lqm.codeproject.site" data-zone="ros"  data-tags='VC6, VC7, VC7.1, Win2K, WinXP, Win2003, STL, Dev, Beginner,rating4.5'></div></td>
		<td class="theme1-background" style="height:94px">&nbsp;</td>
	</tr>
	<tr valign="top">
		<td style="height: 10px;"></td>
		<td style="height: 10px;" class="blank-background"></td>
		<td style="height: 10px;"></td>
	</tr>
</table>


	<a href="#Main"><img alt="Click here to Skip to main content" class="access-link" 
		src="/Images/t.gif" /></a>

	
	<div id="ctl00_TPR" class="sub-headerbar fixed">
	<table cellpadding="0" cellspacing="0" class="extended"><tr><td nowrap="nowrap">
		

<div class="navbar clearfix">
<ul class="navmenu openable">

<li><a id="ctl00_TopNavBar_Home" href="http://www.codeproject.com">home</a>


<li class="openable"><a id="ctl00_TopNavBar_Art" class="down selected" href="/script/Articles/Latest.aspx">articles</a>

	<ul>
		<li class="openable"><a id="ctl00_TopNavBar_ArtTopicList" class="fly" onmouseover="navBarMenu.ShowMap(this, &#39;ctl00_TopNavBar_MapFlyout&#39;);" href="/script/Content/SiteMap.aspx">Chapters and Sections<span class="has-submenu">&gt;</span></a><ul id="ctl00_TopNavBar_MapFlyout">
			<li>
				<div id="siteMap">
					<img src="/images/animated.gif" alt="loading" style="margin:150px;width:100px;height:100px;" />
				</div>
			</li>
			</ul>
		</li>
		<li><a id="ctl00_TopNavBar_ArtSearch" class="fly break" href="/search.aspx">Search</a></li>
		<li><a id="ctl00_TopNavBar_ArtLatestArts" class="fly" href="/script/Articles/Latest.aspx?at=1,3,7">Latest Articles</a></li>
		<li><a id="ctl00_TopNavBar_ArtLatestTips" class="fly" href="/script/Articles/Latest.aspx?at=6">Latest Tips/Tricks</a></li>
		<li><a id="ctl00_TopNavBar_ArtTop" class="fly" href="/script/Articles/TopArticles.aspx?ta_so=5">Top Articles</a></li>
		<li><a id="ctl00_TopNavBar_ArtBeginner" class="fly" href="/search.aspx?aidlst=152&amp;sa_us=True">Beginner Articles</a></li>
		<li><a id="ctl00_TopNavBar_ArtBlogArticles" class="fly break" href="/script/Articles/BlogArticleList.aspx">Technical Blogs</a></li>
		<li><a id="ctl00_TopNavBar_ArtGuide" class="fly" href="/info/Submit.aspx">Posting/Update Guidelines</a></li>
		<li><a id="ctl00_TopNavBar_ArtHelpForum" class="fly" href="/Forums/1641/Article-Writing.aspx">Article Help Forum</a></li>
		<li><a id="ctl00_TopNavBar_ArtCompetition" class="fly break" href="/script/Awards/CurrentCompetitions.aspx?cmpTpId=1">Article Competition</a></li>
		<li><a id="ctl00_TopNavBar_ArtPostArticle" class="fly highlight1" href="/script/Articles/Submit.aspx">
			<img src="/images/write-gr.png" width="19px" height="13px" /> Submit an article or tip
			</a></li>
		<li><a id="ctl00_TopNavBar_ArtPostBlog" class="fly highlight2" href="/script/Articles/BlogFeed.aspx">
			<img src="/images/write-or.png" width="19px" height="13px" /> Post your Blog
			</a></li>		<li class="last"></li>
	</ul>

</li>



<li class="openable"><a id="ctl00_TopNavBar_Answers" href="/script/Answers/List.aspx?tab=active">quick answers</a>
	<ul>
		<li id="ctl00_TopNavBar_AQL"><a id="ctl00_TopNavBar_ArticleQuestion" class="fly highlight1" href="#_comments">
			<img src="/images/write-gr.png" width="19px" height="13px" /> Ask a Question about this 
			article</a>
		</li>

		<li><a id="ctl00_TopNavBar_QAAsk" class="fly highlight2" href="/Questions/ask.aspx"><img 
			src="/images/write-or.png" width="19px" height="13px" /> Ask a Question</a></li>

		
		<li><a id="ctl00_TopNavBar_QAUnanswered" class="fly" href="/script/Answers/List.aspx?tab=unanswered">View Unanswered Questions</a></li>
		<li><a id="ctl00_TopNavBar_QALatest" class="fly" href="/script/Answers/List.aspx?tab=active">View All Questions...</a></li>
		
				<li><a id="ctl00_TopNavBar_QATR_ctl00_Tag" class="fly" href="/script/Answers/List.aspx?tab=active&amp;alltags=true&amp;tags=81" style="padding-left:30px">C# questions</a></li>
			
				<li><a id="ctl00_TopNavBar_QATR_ctl01_Tag" class="fly" href="/script/Answers/List.aspx?tab=active&amp;alltags=true&amp;tags=85" style="padding-left:30px">ASP.NET questions</a></li>
			
				<li><a id="ctl00_TopNavBar_QATR_ctl02_Tag" class="fly" href="/script/Answers/List.aspx?tab=active&amp;alltags=true&amp;tags=842" style="padding-left:30px">VB.NET questions</a></li>
			
				<li><a id="ctl00_TopNavBar_QATR_ctl03_Tag" class="fly" href="/script/Answers/List.aspx?tab=active&amp;alltags=true&amp;tags=308" style="padding-left:30px">C#4.0 questions</a></li>
			
				<li><a id="ctl00_TopNavBar_QATR_ctl04_Tag" class="fly" href="/script/Answers/List.aspx?tab=active&amp;alltags=true&amp;tags=101" style="padding-left:30px">SQL-Server questions</a></li>
			
		<li class="last"></li>
	</ul>

</li>



<li class="openable"><a id="ctl00_TopNavBar_Forums" href="/script/Forums/List.aspx">discussions</a>

	<ul>
		<li><a id="ctl00_TopNavBar_MessageBoardsAll" class="fly" href="/script/Forums/List.aspx">All Message Boards...</a></li>
		<li class="openable"><a class="fly" style="padding-left:30px" href="/Forums/1580997/Application-Lifecycle.aspx">Application Lifecycle<span class="has-submenu">&gt;</span></a>
<ul class="openable"><li><a class="fly" href="/Forums/1533717/Running-a-Business.aspx">Running a Business</a></li>
<li><a class="fly" href="/Forums/1533716/Sales-Marketing.aspx">Sales / Marketing</a></li>
<li><a class="fly" href="/Forums/1651/Collaboration-Beta-Testing.aspx">Collaboration / Beta Testing</a></li>
<li><a class="fly" href="/Forums/3304/Work-Training-Issues.aspx">Work &amp; Training Issues</a></li>
</ul></li>
<li><a class="fly" style="padding-left:30px" href="/Forums/369270/Design-and-Architecture.aspx">Design and Architecture</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/12076/ASP-NET.aspx">ASP.NET</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1580226/JavaScript.aspx">JavaScript</a>
</li>
<li class="openable"><a class="fly" style="padding-left:30px" href="/Forums/1647/C-Cplusplus-MFC.aspx">C / C++ / MFC<span class="has-submenu">&gt;</span></a>
<ul class="openable"><li><a class="fly" href="/Forums/4486/ATL-WTL-STL.aspx">ATL /  WTL / STL</a></li>
<li><a class="fly" href="/Forums/3785/Managed-Cplusplus-CLI.aspx">Managed C++/CLI</a></li>
</ul></li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1827459/Adobe-Technologies.aspx">Adobe Technologies</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1649/Csharp.aspx">C#</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1627782/Free-Tools.aspx">Free Tools</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1827460/Objective-C.aspx">Objective-C</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1832431/Ruby-On-Rails.aspx">Ruby On Rails</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1725/Database.aspx">Database</a>
</li>
<li class="openable"><a class="fly" style="padding-left:30px" href="/Forums/186301/Hardware-Devices.aspx">Hardware &amp; Devices<span class="has-submenu">&gt;</span></a>
<ul class="openable"><li><a class="fly" href="/Forums/1644/System-Admin.aspx">System Admin</a></li>
</ul></li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1606152/Hosting-and-Servers.aspx">Hosting and Servers</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1643/Java.aspx">Java</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1650/NET-Framework.aspx">.NET Framework</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1848626/Android.aspx">Android</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/13695/Mobile.aspx">Mobile</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1540733/Sharepoint.aspx">Sharepoint</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1004257/Silverlight-WPF.aspx">Silverlight / WPF</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1646/Visual-Basic.aspx">Visual Basic</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/Forums/1640/Web-Development.aspx">Web Development</a>
</li>
<li><a class="fly" style="padding-left:30px" href="/suggestions.aspx">Site Bugs / Suggestions</a>
</li>

		<li class="last"></li>
	</ul>

</li>




<li class="openable"><a id="ctl00_TopNavBar_Features" href="/Feature/">features</a>

	<ul>
        
		<li><a id="ctl00_TopNavBar_CPTV" class="fly highlight1" href="http://CodeProject.TV"><img src="/images/CPTV-24.png" width="24px" 
                height="24px" alt="CP.TV" style="vertical-align:text-bottom"/>CodeProject.TV</a></li>
        <li><a id="ctl00_TopNavBar_DiscussCPTV" class="fly break" href="/Forums/1829610/CodeProject-TV.aspx">Discuss CodeProject.TV</a>
		<li><a id="ctl00_TopNavBar_Catalog" class="fly" href="/script/Catalog/List.aspx">Component & Service Catalog</a></li>
		<li><a id="ctl00_TopNavBar_Comps" class="fly" href="/script/Awards/CurrentCompetitions.aspx?cmpTpId=1&amp;awsac=true">Competitions</a></li>
		<li><a id="ctl00_TopNavBar_News" class="fly" href="/script/News/List.aspx">News</a></li>
		<li><a id="ctl00_TopNavBar_Insider" class="fly" href="/Feature/Insider/">The Insider Newsletter</a></li>
    	<li><a id="ctl00_TopNavBar_DailyBuild" class="fly" href="/Feature/DailyBuild">The Daily Build Newsletter</a></li>
		<li><a id="ctl00_TopNavBar_Newsletters" class="fly" href="/script/Mailouts/Archive.aspx?mtpid=1">Newsletter archive</a></li>
		<li><a id="ctl00_TopNavBar_Surveys" class="fly" href="/script/Surveys/List.aspx">Surveys</a></li>
		<li><a id="ctl00_TopNavBar_Showcase" class="fly" href="/KB/showcase/">Product Showcase</a></li>
		<li><a id="ctl00_TopNavBar_Research" class="fly" href="/script/ResearchLibrary/Index.aspx">Research Library</a></li>

		
		<li><a id="ctl00_TopNavBar_Stuff" class="fly" href="/Info/Stuff.aspx">CodeProject Stuff</a></li>
		<li class="last"></li>
	</ul>

</li>


<li  class="openable"><a id="ctl00_TopNavBar_Lounge" href="/Lounge.aspx">community</a>

	<ul>
		<li><a id="ctl00_TopNavBar_InsiderLnk" class="fly" href="/insider.aspx/988106/GeneralObject]">The Insider News</a></li>
		<li><a id="ctl00_TopNavBar_LoungeLnk" class="fly" href="/Lounge.aspx">The Lounge  </a></li>
		<li><a id="ctl00_TopNavBar_WeirdWonderful" class="fly" href="/Feature/WeirdAndWonderful.aspx">The Weird & The Wonderful</a></li>
		<li><a id="ctl00_TopNavBar_SoapBoxLnk" class="fly" href="/Forums/1536756/The-Soapbox.aspx">The Soapbox</a></li>
		<li><a id="ctl00_TopNavBar_PRLnk" class="fly break" href="/Forums/1738007/Press-Releases.aspx">Press Releases</a></li>
		<li><a id="ctl00_TopNavBar_WhosWho" class="fly" href="/script/Membership/Profiles.aspx">Who's Who</a></li>
		<li><a id="ctl00_TopNavBar_MVPs" class="fly" href="/script/Awards/MVPWinners.aspx">Most Valuable Professionals</a></li>
		<li><a id="ctl00_TopNavBar_Companies" class="fly break" href="/script/Membership/Profiles.aspx?mgtid=1&amp;mgm=True">Company Listings</a></li>

		
		<li class="openable"><a class="fly" href="/Forums/1580229/Hindi.aspx">Non-English Language
			<span class="has-submenu">&gt;</span></a>
		<ul>
		<li><a class="fly" href="/Forums/1580229/Hindi.aspx">General Indian Topics</a></li>
		<li><a class="fly" href="/Forums/1580230/Chinese.aspx">General Chinese Topics</a></li>
		</ul>
		<li class="last"></li>
		
	</ul>

</li>


<li class="openable" style="margin-left:20px"><a id="ctl00_TopNavBar_Help" href="/KB/FAQs/">help</a>

	<ul>
		<li><a id="ctl00_TopNavBar_HelpWhatIs" class="fly" href="/info/guide.aspx">What is 'CodeProject'?</a></li>
		<li><a id="ctl00_TopNavBar_HelpGeneral" class="fly break" href="/KB/FAQs/">General FAQ</a></li>
		<li><a id="ctl00_TopNavBar_HelpPostQuestion" class="fly break highlight1" href="/Questions/ask.aspx">Ask a Question</a></li>
		<li><a id="ctl00_TopNavBar_HelpBugs" class="fly" href="/suggestions.aspx">Bugs and Suggestions</a></li>
		<li><a id="ctl00_TopNavBar_HelpArticles" class="fly" href="/Forums/1641/Article-Writing.aspx">Article Help Forum</a></li>
		<li><a id="ctl00_TopNavBar_HelpSiteMap" class="fly" href="/script/Content/SiteMap.aspx">Site Map</a></li>
		<li><a id="ctl00_TopNavBar_HelpAdvertise" class="fly" href="http://developermedia.com/">Advertise with us</a></li>
		<li><a id="ctl00_TopNavBar_HelpJobs" class="fly" href="/info/Jobs/">Employment Opportunities</a></li>
		<li><a id="ctl00_TopNavBar_HelpAboutUs" class="fly" href="/info/about.aspx">About Us</a></li>
		<li class="last"></li>
	</ul>

</li>

</ul>

</div>
	</td><td align="right">
		

<div class="searchbar">

<form method="get" action="/search.aspx" name="Search" class="tight">


<table border="0" cellspacing="0" cellpadding="0" class="search"><tr><td><input TabIndex="2" class="search highlight" id="sb_tb" value="thompson nfa javascript" name="q" /></td><td><input type="image" src="/images/search.gif" /></td></tr></table>

<div class="hover-container">
	<div id="SearchFilter" class="search-advanced popup small-text align-left">
	<b>Search within:<br /></b>
		
		<input type="radio" id="sb_kw" name="sbo" value="kw" checked="true"><label for="sb_kw">Articles</label><br>
<input type="radio" id="sb_vkw" name="sbo" value="vkw"><label for="sb_vkw">Videos</label><br>
<input type="radio" id="sb_qa" name="sbo" value="qa"><label for="sb_qa">Quick Answers</label><br>
<input type="radio" id="sb_fm" name="sbo" value="fm"><label for="sb_fm">Messages</label><br>
<input type="radio" id="sb_ctlk" name="sbo" value="ctlk"><label for="sb_ctlk">Product Catalog</label><br>


		
		
	</div>
</div>
</form>

</div>
	</td></tr></table>
	<div class="sub-headerbar-divider"></div>
	</div>
	

	<div id="A" class="container-content-wrap fixed"> 

	<div itemscope itemtype="http://schema.org/Article" class="container-content"> 

		<div class="clearfix">
			<div class="float-left container-breadcrumb">
				<div><a href="/script/Content/SiteMap.aspx">Articles</a> &#187; <a href="/Chapters/6/General-Programming.aspx">General Programming</a> &#187; <a href="/KB/recipes/"><span itemprop="articleSection">Algorithms & Recipes</span></a> &#187; <a href="/KB/recipes/#Parsers">Parsers</a></div>
			</div>

			<div class="align-left float-right padded-top">
				


 
&nbsp;










			</div>

			<div class="float-right container-breadcrumb article-nav">
				
<div class="">


<a id="ctl00_PrevNext_NextLink" title="Next" href="/script/Articles/PrevNextLookup.aspx?aid=5412&amp;at=1&amp;secId=57" style="margin-left:5px">Next</a>
<img id="ctl00_PrevNext_NextImg" title="Next" rel="nofollow" src="/Images/arrow-right.png" style="border-width:0px;vertical-align:bottom;" />
</div>
			</div>

			<div class="align-right float-left">
				
			</div>
		</div>

		<table class="extended container-article-parts" cellpadding="0" cellspacing="0"><tr valign="top">
		<td>

			<div id="ctl00_Nav" class="container-article-tabs">
				<div class="tabs">
					

<div class="">
	<div class="selected">Article</div><div class="unselected"><a href="/script/Articles/ViewDownloads.aspx?aid=5412">Browse Code</a></div><div class="unselected"><a href="/script/Articles/ViewTasks.aspx?aid=5412">Bugs / Suggestions</a></div><div class="unselected"><a href="/script/Articles/Statistics.aspx?aid=5412">Stats</a></div><div class="unselected"><a href="/script/Articles/ListVersions.aspx?aid=5412">Revisions</a></div><div class="unselected"><a href="/script/Articles/ListAlternatives.aspx?aid=5412">Alternatives</a></div>

	<!-- anchorLink used to auto-link to comments at end of article -->
	<div class="unselected"><a href="WebControls/#_comments" id="ctl00_ArticleTabs_CommentLink" class="anchorLink">Comments 
        <span id="ctl00_ArticleTabs_CmtCnt">(322)</span></a>
	</div>

    <div id="ctl00_ArticleTabs_WorkspaceLinks" class="related-link-box padded-top">
        <a href="https://workspaces.codeproject.com/amer-gerzic/writing-own-regular-expression-parser" id="ctl00_ArticleTabs_WorkspaceHeader"><img alt="Workspaces" 
            src="/images/OpenWithWS.gif" style="width:119px;height:146px;border:0" /></a>
            
            
        <img alt="Workspaces" src="/images/Workspaces-150x25.png" style="width:100px;height:18px" />
        <div class="unselected"><a href="https://workspaces.codeproject.com/amer-gerzic/writing-own-regular-expression-parser" id="ctl00_ArticleTabs_WorkspaceLink">View this Workspace</a></div>
        <div class="unselected"><a href="https://workspaces.codeproject.com/amer-gerzic/writing-own-regular-expression-parser/fork" id="ctl00_ArticleTabs_WorkspaceFork">Fork this Workspace</a></div>

        <a id="ctl00_ArticleTabs_A1"><img alt="Workspaces" class="padded-top"
            src="/images/git-86x36.png" style="width:43px;height:18px" /></a>

        <div class="unselected"><a href="/script/Articles/ViewDownloads.aspx?aid=5412" id="ctl00_ArticleTabs_GitLink">Connect using Git</a></div>
	</div> 
</div>	

				</div>

				

	    		
				<div>
					

<div class="social-bookmarks">
<h3>Share</h3>
<div class="popup-bar">
    <div class="linkedin-icon"></div>
    <div class="popup-bar-flyout">
        <span class="linkedin"><script src="//platform.linkedin.com/in.js" type="text/javascript">
lang: en_US
</script>
<script type="IN/Share" data-counter="right" data-showzero="true"></script></span>
    </div>
</div>
<div class="popup-bar">
    <div class="google-icon"></div>
    <div class="popup-bar-flyout">
        <span class="google"><div class="g-plusone" data-size="medium"></div></span>
    </div>
</div>
<div class="popup-bar">
    <div class="facebook-icon"></div>
    <div class="popup-bar-flyout">
        <span id="fb-wrap" class="facebook" style=";overflow:hidden"><div id="fb-root"></div><div class="fb-like" data-href="http://www.codeproject.com/Articles/5412/Writing-own-regular-expression-parser" data-send="false" data-layout="button_count" data-width="450"  data-show-faces="false" data-font="segoe ui"></div></span>
    </div>
</div>
<div class="popup-bar">
    <div class="twitter-icon"></div>
    <div class="popup-bar-flyout">
        <span class="twitter"><a href="https://twitter.com/share" class="twitter-share-button" data-hashtags="CodeProject"></a></span>
    </div>
</div>

</div>
				</div> 
    			

			</div>

		</td>
		<td>
			
			<div id="AT" class="container-article  fixed"> 
				<div class="article">

                    <a href="https://workspaces.codeproject.com/amer-gerzic/writing-own-regular-expression-parser" id="ctl00_ForkRibbon" class="fork-ribbon"><img alt="Workspaces" 
                        src="/images/OpenInWS-ribbon.gif" style="width:122px;height:122px;border:0" /></a>

					<form name="aspnetForm" method="post" action="/Articles/5412/Writing-own-regular-expression-parser" id="aspnetForm" style="margin:0;padding:0">
<div>
<input type="hidden" name="__VIEWSTATE" id="__VIEWSTATE" value="/pnwathKWStqD43KRI4rkIdE6f26xPAo9kah4H5vvL3xRlGBEWECZ3hc8Qd05PY1q9Gm3IRh9k3onyZlYkKccOLBc2LTqw95BcCuCATdfn4uig1hGhIgV7toNW8yIGZTKjGMlgV8ut+pyKMQREgWzt6qlZmN4bU2tCYR3s0zvYtFUWVojf7DsOPrfwfJYa47fHUsv2lPULYYUba3zQU0TCuG+KdLDlHZ7ZWSR8AwR4lHVTLY6ACs8O5UVmtG1HqIzrQvmmkk4dHVOlPnrVJcWeHd2vH9miKkndKdoprAtfLseIzDiuH7fjohYYmyof1+5x6ldsvHK7RhCudu8mvQTf+6PVYj7q85kPBnAJHECAyKgu4w0y1ouOp4PHdbYtNpO/iyQLxqNcSx6TTSjwCOwqTgEJLOKiv9lDwzOapwr0wmhjZwGlHS3A9pOjEJ/Vc1B9C+K4ld6jjEZyCHeUwkOn98EiW40kARa7baUEyVdoaOs3fXzj6kuN/27PHxbf/GgsswBXvPyQeUyuQ4TpX5W81acAmzR1ruHyDUfHOIG09/g3FY24mRtKHdfb/zHjdZ/snkY3pmZx5AmZ4nYvlxi+5OmI0c+d7pj3Ne1Uire/Sz5dF8LF5+GbsR0uYBiTIvpw54ueCU9vWwFIX+n07yyN32IgrQq+OhArKpb1Gn0EgsD0oR+SxQJGYJhVX2AEE4J2/aKH56w5z69zwZaZCl0px1+QEwy6aTBQXeZXvu4s80RSTBTABE3UL4/39CoRJeW9boFfNBhTvWseVR5qidql/BFjQtU6inMi3Yh62VKdKUSKF92WJiPYGpjNgok4VeQWzRzclQ6N+i7nX2xmkIXvuvDaoScEvf/I5WsYb8Ld7X/crJZep3ckS7DXoGiGpbiVDcUzfr+9pjLOGyw/vlQqG2QAVJ1Igd6gN6zG67iQfHvwY/xNJqcezIxO3vp8fEEIOk5CX642/OhE+TmWZsw9r378jRoJ3ZJWyNzzZBcXajYey9xosWv1V4r6BTDDmyCqJPf5frbCRyjwyYo3vFgrKnOfU5QCzjHEUWXH0n9m21DdLcD5Bm+Ae5IHIkiVRukkMuaejucxv/NGBdtm/jZLvegt14J6eRTz1cBouHRxu/F59r7zl4l1Bxa2B+vGSdS6S5ugDwztPjS5Fcu/mZR8UIuPTM9u61RGQvNPQp+zdNOFTlKFYX441x6SY2JORZabTNFwqnpYcBcWFTSGEKx2F8EwbfvLZfiP+327HseMZ/ukA1e4gUx6tspRr6MUpfyLLEOPVV0bgVBI7L98AH7hQLKb3mX1xdyL3tYD3m0gOsm1NzYrBzHX/IzSZjNIYB/PL6a/BmL7PSqhyRxae37f75m+/gOBEDW25tUMDuZneiF/+e50ut486hWH5ugVtoPU/etzTdJFpWacRZaClzwu/mj1LuWa+RsB2WpRNL+BVny73so9FXxQ0/DZ1H2bs9Bc6s7TWFNDa1oLULLUs+Xyko420t8+ytTFY8cTU1FQKCsnRibLCtmYKNzhz5VHPgsbU7lTIp/7Ijk7d4nkYvTJWdVssp/iYC1h0pqtSAjWBCo2Yltk0+O6ILct7SbdqMcVvzSEedBUZCsILpUvr1HfNiO0rFduaAUA3YlqvYxXbF+Huv79cxFN7mL0M8AH3754y0qIQlbBtUOCp4c3o5CzWKrKr018AVSAzXe7ly26AeV6YKsn3c6/u4lc584KwaPW2S+AKibmvo2KUdO6lUUfoM5FaB13e0M60gZnjojLXmyn60ngjJMFZNge+0NBO/nXHCBS6S8M1FiVQ3cknp6TD98cjs2TV53e6b7nyz2zxmUkGqd5rei6xKOjteomD/6FqO3WS1myWCFMcM6fBUgojcmpkGmIY6ZQQgx0M92/KP3aB3rwjiwSHEu5Rz+90iyY0yXxR/ViGiQ8mFnNZSLHdZ8Q/ZDE/xBXVTw+01JykeME6Sr+zdz9UBRXgb3/h8lKByYH9NmUblyiGzm1vGFZLCzO9A61aAN09ptHyCq6IXY9GwEOZz7/0bSQ/rJdkL3P1RfyV6KAUvnppwU8KIBfUF11I/HGGwc0HUR6Iqu1V+hzqkrGDkBa4dM4DuErM7hOQjNaXsXJiUZfk2ri4agoguOMy5QQCkmPAlILGLe/iQM+dvVffDmQVLFP3FMBsvFI9YLnv7VCO5d6EHEQS2cp/S4rzP3LT+AkSux2wqgoU83oT9coMrswaoSgEgVTNQC/34X6RB7H41xalx2r1uCFmtlYDMqdvzYhcN3oEyTiXJjqpVphPr+wEUKxOqUf03lB94Zs2tpAqTdhVkCTSxrxSVvLhAGLnly6nlxmI1RbWEMMNPo7ZTAvDJRfI8+Vk1emJDRw==" />
</div>


					
					 
					<div class="header">

					<a name="Main"></a>

					
					<a name="_articleTop" id="_articleTop"></a>
					<div class="title">
					
					
					<h1 id="ctl00_ArticleTitle" itemprop="name">Writing own regular expression parser</h1> 
					</div>

					
					<div class="entry">
						By <span class="author"><a href="/script/Membership/View.aspx?mid=30261" rel="author"><span itemprop="author" itemscope itemtype="http://schema.org/Person"><span itemprop="name">Amer Gerzic</span></span></a></span>, 
						<span class="date" itemprop="dateModified" content="2003-11-15 00:00:00">
							14 Nov 2003</span>
			
									
					</div>

					
					<table class="voting-bar"><tr><td nowrap="nowrap">
						<div id="ctl00_CurRat" class="tooltip anchorLink" style="cursor:pointer" name="CurRat_5412">
				
							

<table cellpadding="0" cellspacing="0" class="small-text" itemprop="aggregateRating" itemscope itemtype="http://schema.org/AggregateRating"> 
<tr>
	
	<td class="nowrap">

		
			<meta itemprop="bestRating" content="5"> 
			<meta itemprop="worstRating" content="1">
		

		<span id="ctl00_ArticleRating_VI">
		<div class="nowrap rating-stars-large" style="height:19px;width:119px;position:relative;">
	<div class="clipped align-left float-left" style="height:19px;width:117px;">
		<img src="http://s.codeproject.com/script/Ratings/Images/stars-fill-lg.png" style="border-width:0px;" />
	</div><div class="clipped" style="height:19px;width:2px;position:relative;">
		<img src="http://s.codeproject.com/script/Ratings/Images/stars-empty-lg.png" style="border-width:0px;position:absolute;top:0;right:0;" />
	</div>
</div>
		</span>

		
	</td>
	
	<td id="ctl00_ArticleRating_VR" class="nowrap">
		&nbsp;
		<span id="ctl00_ArticleRating_VotesR">&nbsp;<span itemprop="ratingValue" class="rating">4.91</span> (<span itemprop="ratingCount" class="count">121</span> votes)</span>
		
	</td>

</tr>

</table>


							<div id="ctl00_RB" class="speech-bubble-container-up">
								<div class="speech-bubble-up" style="width:150px !important">
									            
<div>
<table class="feature" width="100%" height="50px" title="Voting Distribution. Recent data only" cellpadding="0" cellspacing="0"><tr class="chart-row"><td class="chart-column rating-ignore-vote" title="Outside deviation limits - not included in score."><img src="/script/Ratings/Images/pollcol.gif" width="20pxpx" height="1px" border="0px" alt="3 votes, 2.5%" title="3 votes, 2.5%" /><br /><span title="3 votes">1</span></td>
<td class="chart-column rating-ignore-vote" title="Outside deviation limits - not included in score."><img src="http://s.codeproject.com/Images/t.gif" width="20pxpx" height="1px" border="0px" alt="" title="" /><br /><span title="0 votes">2</span></td>
<td class="chart-column rating-ignore-vote" title="Outside deviation limits - not included in score."><img src="/script/Ratings/Images/pollcol.gif" width="20pxpx" height="1px" border="0px" alt="1 vote, 0.8%" title="1 vote, 0.8%" /><br /><span title="1 vote">3</span></td>
<td class="chart-column"><img src="/script/Ratings/Images/pollcol.gif" width="20pxpx" height="4px" border="0px" alt="10 votes, 8.3%" title="10 votes, 8.3%" /><br /><span title="10 votes">4</span></td>
<td class="chart-column"><img src="/script/Ratings/Images/pollcol.gif" width="20pxpx" height="50px" border="0px" alt="107 votes, 88.4%" title="107 votes, 88.4%" /><br /><span title="107 votes">5</span></td>
</tr></table><div class="small-text align-center">4.91/5 - 121 votes</div><div class="small-text align-center subdue">4 removed</div><div class="small-text align-center subdue">μ 4.78, σ<sub>a</sub> 1.21 [<a href="/KB/FAQs/RatingReputationFAQ.aspx#noisefilter">?</a>]</div>
</div>
								</div>
								<div class="speech-bubble-pointer-up">
									<div class="speech-bubble-pointer-up-inner"></div>
								</div>
							</div>
						</div>
					</td>
					<td nowrap>
						
					</td>
					<td id="ctl00_RateArticleRow" class="voting-bar">
							
							<div class="float-right align-right">
								<div id="ctl00_RateArticle_RateItemWrapper" class="container-rating small-text" name="RateItem_5412">

	<table width="100%" cellpadding="0" cellspacing="0" class="small-text">
	<tr>
		<td id="ctl00_RateArticle_VoteResultDiv" class="rating-result align-right">
			<span class="align-right"></span>
			<img class="loaderImg" width="16px" alt="loading..." height="16px" 
				src="/Images/animated_loading_blue.gif" style="display:none;" /> 
		</td>

	
		<td class="voteTbl" style="white-space:nowrap" align="right">
			<table class="small-text">
			<tr>
				<td id="ctl00_RateArticle_RateText" class="rating-prompt">
					Rate this:
				</td>

				
				<td id="ctl00_RateArticle_VoteFormDiv" class="nowrap rating-stars-voter-large">
					

					<span id="ctl00_RateArticle_RB" class="tooltip ajaxHist radio voting">
						<span id="ctl00_RateArticle_VoteRBL"><input id="ctl00_RateArticle_VoteRBL_0" type="radio" name="ctl00$RateArticle$VoteRBL" value="1" /><input id="ctl00_RateArticle_VoteRBL_1" type="radio" name="ctl00$RateArticle$VoteRBL" value="2" /><input id="ctl00_RateArticle_VoteRBL_2" type="radio" name="ctl00$RateArticle$VoteRBL" value="3" /><input id="ctl00_RateArticle_VoteRBL_3" type="radio" name="ctl00$RateArticle$VoteRBL" value="4" /><input id="ctl00_RateArticle_VoteRBL_4" type="radio" name="ctl00$RateArticle$VoteRBL" value="5" /></span> 

						
					</span>

				</td>

				
				<td style="padding-left:5px">	
					<input type="submit" name="ctl00$RateArticle$SubmitRateBtn" value="Vote!" id="ctl00_RateArticle_SubmitRateBtn" class="button" />
				</td>
			</tr>
			</table>
			
		</td>
	</tr>
	</table>
	<div class="hover-container">
		
        <div id="ctl00_RateArticle_RSU" class="rating-comment align-left float-right">
            <div class="padded">
            Please <a id="ctl00_RateArticle_SignUp" href="https://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign up or sign in</a> to vote.
            </div>
        </div>
	</div>
</div>
							</div>
												
					</td>

					</tr></table>

					</div>
					
					


					
					

					
					
					

						
					

					

						
						<div id="contentdiv" class="text" itemprop="articleBody">
						



<UL class=download>
<LI><A href="/KB/recipes/OwnRegExpressionsParser/RegExSource.zip">Download source files - 8.48 Kb</A> 
<LI><A href="/KB/recipes/OwnRegExpressionsParser/RegExDemo.zip">Download demo project - 22.9 Kb</A> </LI></UL>
<P><IMG height=223 alt="Sample Image - RegExDemo.jpg" src="/KB/recipes/OwnRegExpressionsParser/RegExDemo.jpg" width=600></P>
<H2>Introduction</H2>
<P>Have you ever wondered how regular expressions work in detail? If the answer is yes then this article is right for you. I will try to guide you step by step on how to create your own mini regular expression library. The purpose of the article is NOT to give you a highly optimized, tested and great regular expression library, but to explain principals behind the pattern matching in text files. If you only want a good library and don't care how it works, you probably want Boost regex library, which you can find <A href="http://www.boost.org/" target=_blank>here.</A> I used a couple of different regular expression libraries but I must say that I am happiest with Boost regex. Obviously you decide it for yourself. There is another regular expressions article here on CP which could be found <A href="http://www.codeproject.com/cpp/rexsearch.asp">here</A>. I must admit, I did not read the article completely but it seems to me that the article focuses mostly on how to use the regular expression library provided by the author. In this article, the author uses similar technique (I could be wrong though) to create a more sophisticated library. The article you are reading right now, could be seen as a prerequisite for the article I just mentioned above.</P>
<P>Regular expressions are part of MS .NET library or Java SDK (if you write code in Java). As you can see, regular expressions are available in many different programming languages and technologies. Actually the article does not focus on writing the library in a specific language. I wrote the code in C++, using STL primarily because it is my favorite language/library, but the principles from the article could be applied to any language (obviously). I will try to be as language independent as possible, using pseudo code where ever possible. If you want the code in Java, please send me an email. The code provided here in this article is free (obviously) but if you like it and use it in your application, it would be great if you would give me the credit for what I deserve. Also please email me, so I can show off to my peers and/or potential employers.</P>
<H2>Overview</H2>
<P>So how are we going to do it? Well before we start with coding, it is necessary to explain the mathematical background needed to fully understand the method used here in this article. I would strongly recommend to read and understand the math behind, because once we overcome the math part, the rest will be very simple. Note however that I will not have any mathematical proofs. If you are interested in proofs, please check out the references, which could be found in <A href="#Eight">References</A> section of this article. Additionally, note that the regular expression parser, which we will create here will support these three operations:</P>
<OL>
<LI>Kleen Closure or Star operator ("*") 
<LI>Concatenation (For example: "ab") 
<LI>Union operator (denoted with character "|") </LI></OL>
<P>However many additional operators can be simulated by combining these three operators. For instance:</P>
<OL>
<LI>A+ = AA* (At least one A) 
<LI>[0-9] = (0|1|2|3|4|5|6|7|8|9) 
<LI>[A-Z] = (A|B|...|Z), etc. </LI></OL>
<P>The reason for implementing only three operators is simplicity. When I started planning to write this article, I quickly recognized that I had to limit myself in many ways. The topic is so large, that it would require a book to explain every little detail (maybe I will write it someday). As I stated above, the purpose of the article is not to equip you with a library but to introduce you to principles behind regular expressions. If you want to know more on how to use regular expressions, then you can check out the book: Mastering Regular Expressions - O'Reilly.</P>
<P>Following is the overview of the article:</P>
<OL>
<LI><A href="#One">What is NFA?</A> 
<LI><A href="#Two">What is DFA?</A> 
<LI><A href="#Three">Thompson's Algorithm</A> 
<LI><A href="#Four">Subset Construction Algorithm</A> 
<LI><A href="#Five">DFA optimization</A> 
<LI><A href="#Six">Using the results from parts above</A> 
<LI><A href="#Seven">Final Words</A> 
<LI><A href="#Eight">Reference</A> </LI></OL>
<H2><A name=One>What is NFA?</A></H2>
<P>NFA stands for <B>nondeterministic finite-state automata</B>. NFA can be seen as a special kind of final state machine, which is in a sense an abstract model of a machine with a primitive internal memory. If you want to know more about finite-state machines, please refer to <A href="#Eight">References</A> section below.</P>
<P>Let us look at the mathematical definition of NFA.</P>
<P>An NFA <CODE>A</CODE> consists of:</P>
<BLOCKQUOTE>
<OL type=a>
<LI>A finite set <CODE>I</CODE> of input symbols 
<LI>A finite set <CODE>S</CODE> of states 
<LI>A next-state function <CODE>f</CODE> from <CODE>S</CODE> x <CODE>I</CODE> into <CODE>P(S)</CODE> 
<LI>A subset <CODE>Q</CODE> of <CODE>S</CODE> of accepting states 
<LI>An initial state <CODE>s0</CODE> from <CODE>S</CODE> </LI></OL>
<P>denoted as <CODE>A(I, S, f, Q, s0)</CODE></P></BLOCKQUOTE>
<P>If we would explain the above definition to a 12 year old, we could say that an NFA is a set <CODE>S</CODE> of states that are connected by function <CODE>f</CODE> (maybe to a smarter 12 year old). NFAs are represented in two formats: Table and Graph. For example, let us look at the table representation:</P>
<TABLE width="100%" border=1>
<TBODY>
<TR>
<TH width="12%">
<P>Input</P>
<P>States</P></TH>
<TH width="15%">a</TH>
<TH width="17%">b</TH>
<TH width="15%">c</TH>
<TH width="17%">d</TH>
<TH width="24%">Epsilon</TH></TR>
<TR>
<TD><CODE>s0</CODE></TD>
<TD>
<DIV align=center><CODE>s1</CODE>,<CODE>s3</CODE></DIV></TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD></TR>
<TR>
<TD><CODE>s1</CODE></TD>
<TD>&nbsp;</TD>
<TD>
<DIV align=center><CODE>{s2}</CODE></DIV></TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD></TR>
<TR>
<TD><CODE>{s2}</CODE></TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD></TR>
<TR>
<TD><CODE>s3</CODE></TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>
<DIV align=center><CODE>s4</CODE>,<CODE>s5</CODE></DIV></TD></TR>
<TR>
<TD><CODE>s4</CODE></TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>
<DIV align=center><CODE>{s6}</CODE></DIV></TD>
<TD>&nbsp;</TD></TR>
<TR>
<TD><CODE>s5</CODE></TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>
<DIV align=center><CODE>{s7}</CODE></DIV></TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD></TR>
<TR>
<TD><CODE>{s6}</CODE></TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD></TR>
<TR>
<TD><CODE>{s7}</CODE></TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD>
<TD>&nbsp;</TD></TR></TBODY></TABLE>
<P>An equivalent graph would be:</P>
<P align=center><IMG height=471 src="/KB/recipes/OwnRegExpressionsParser/graph1.jpg" width=329></P>
<P>Looking at the table/graph above, we can see that there are special transitions called Epsilon transitions, which is one of the special features of NFA. A transition is an event of going from one state to another. Epsilon transition is a transition from one state to another on an empty string. In other words, we are going from one state to another on no character input. For example, as we can see from table/graph above, we can go on no input from <CODE>s3</CODE> to <CODE>s4</CODE> and <CODE>s5</CODE>, which means that we have a <B>choice</B>. Similarly, there is a <B>choice</B> to go from state <CODE>s0</CODE> to states <CODE>s1</CODE> or <CODE>s3</CODE> on character input <CODE>a</CODE>. Hence the name <B>nondeterministic</B>, because at some point, the path which we are able to go is not unique but we have a <B>choice</B>. The final and accepting states are drawn double circled (or enclosed in "{}" in the table), like for example <CODE>s6</CODE>. Once one of these states is reached, we have an accepting state, and hence an accepting character string.</P>
<P>In an NFA, like the mathematical definition defines, there is always a starting state. I used Graphvis, a great tool for drawing different kinds of graphs (see <A href="#Eight">References</A> section), for drawing of NFAs and DFAs (see later). Because Graphvis is laying out the nodes of a graph on its own, it seems to me that a starting state is always the state drawn at the top of the graph. So we will follow that convention.</P>
<H2><A name=Two>What is DFA?</A></H2>
<P>DFA stands for <B>deterministic finite state automata</B>. DFA is very closely related to NFA. As a matter of fact, the mathematical definition of NFA works for DFA too. But obviously there are differences, from which we will take advantage. One big difference is that in a DFA there are no Epsilon transitions. Additionally, for each state all transitions leading away from this state are done on different input characters. In other words, if we are in state <CODE>s</CODE>, then on input character <CODE>a</CODE>, there is a unique transition on that character from <CODE>s</CODE>. Additionally, in a DFA all states must have a valid transition on an input character. Input character here is finite set <CODE>I</CODE> of input symbols (like in mathematical definition). For example, in the above graph (under DFA), the set of symbols <CODE>I</CODE> would be <CODE>{a,b,c,d}</CODE>.</P>
<P>Now that we understand NFAs and DFAs, we can proceed by saying that given any NFA, there is an equivalent DFA (You are going to have to trust me on this because I don't think it is appropriate to give you the mathematical proof of this statement). As humans, generally it is easier for us to construct an NFA, as well as interpret what language an NFA accepts. But why do we need the DFAs then? Well if we think about computers, it is very hard to "teach" them to do very well educated guesses (sometimes even we can't make smart educated guesses). And this is exactly what the computer needs to do, when traversing an NFA. If we would write an algorithm, which would use an NFA to check for an accepting combination of characters, it would involve backtracking to check for choices that it did not make previously. Obviously, there are regular expression parsers which work using NFAs, but they are generally slower than those that use DFAs. This is due to the fact that a DFA has a unique path for each accepting string, so no backtracking is involved. Hence, we are going to use a DFA to check if a combination of input characters is accepted by an automata.</P>
<P><B>Note</B>: If you really want to understand both NFAs and DFAs, I would recommend to do further reading on these topics. It is useful as an exercise to convert from one to another, to fully understand the difference and the algorithm used here to convert NFA to DFA (see later).</P>
<H2><A name=Three>Thompson's Algorithm</A></H2>
<P>Now that we have all the mathematical background that we need to understand regular expressions, we need to start thinking about what is our goal. As a first step, we realize that we need a way of going from a regular expression (like <CODE>ab*(a|b)*</CODE>) to a data structure, which will be easy to manipulate and use for pattern matching. But let us first look at the method for converting a regular expression to an NFA. Probably the most famous algorithm for doing this conversion is Thompson's algorithm. This algorithm is not the most efficient, but it ensures that any regular expression (assuming that its syntax is correct) will be successfully converted to an NFA. With the help of the basic NFA as seen from figure below, we can construct any other:</P>
<P align=center><IMG height=130 src="/KB/recipes/OwnRegExpressionsParser/basicNFA.jpg" width=170></P>
<P>Using the basic elements above, we will construct three operations, which we would like to implement in our regular expression parser like the following:</P>
<P align=center><IMG height=400 src="/KB/recipes/OwnRegExpressionsParser/Thompson.jpg" width=450></P>
<P>But how do we go from something like <CODE>(a|b)*ab</CODE> to the graph above? If we consider what we really need to do, we can see that evaluating regular expressions is similar to evaluating arithmetic expressions. For example, if we would like to evaluate <CODE>R=A+B*C-D</CODE>, we could do it like:</P>
<BLOCKQUOTE>
<P>PUSH A</P>
<P>PUSH B</P>
<P>PUSH C</P>
<P>MUL</P>
<P>ADD</P>
<P>PUSH D</P>
<P>SUB</P>
<P>POP R</P></BLOCKQUOTE>
<P>Here <CODE>PUSH</CODE> and <CODE>POP</CODE> are stacks and <CODE>MUL</CODE>, <CODE>ADD</CODE> and <CODE>SUB</CODE> take 2 operands from the stack and do the corresponding operation. We could use this knowledge for constructing an NFA from a regular expression. Let's look at the sequence of operations that need to be performed in order to construct an NFA from a regular expression <CODE>(a|b)*cd</CODE>:</P>
<BLOCKQUOTE>
<P>PUSH a</P>
<P>PUSH b</P>
<P>UNION</P>
<P>STAR</P>
<P>PUSH c</P>
<P>CONCAT</P>
<P>PUSH d</P>
<P>CONCAT</P>
<P>POP R</P></BLOCKQUOTE>
<P>As we can see, it is very similar to the evaluation of arithmetic expressions. The difference is that in regular expressions the star operation pops only one element from the stack and evaluates the star operator. Additionally, the concatenation operation is not denoted by any symbol, so we would have to detect it. The code provided with the article simplifies the problem by pre-processing the regular expression and inserting a character ASCII code 0x8 whenever a concatenation is detected. Obviously it is possible to do this "on the fly", during the evaluation of the regular expression, but I wanted to simplify the evaluation as much as possible. The pre-processing does nothing else but detects a combination of symbols that would result in concatenation, like for example: <CODE>ab</CODE>, <CODE>a(</CODE>, <CODE>)a</CODE>,<CODE>*a</CODE>,<CODE>*(</CODE>, <CODE>)(</CODE>. </P>
<P><CODE>PUSH</CODE> and <CODE>POP</CODE> operations actually work with a stack of simple NFA objects. If we would <CODE>PUSH</CODE> symbol <CODE>a</CODE> on the stack, the operation would create two state objects on the heap and create a transition object on symbol <CODE>a</CODE> from state 1 to state 2. Here is the portion of the code that pushes a character on the stack:</P><PRE><span class="code-keyword">void</span> CAG_RegEx::Push(<span class="code-keyword">char</span> chInput)
{
    <span class="code-comment">//</span><span class="code-comment"> Create 2 new states on the heap
</span>    CAG_State *s0 = <span class="code-keyword">new</span> CAG_State(++m_nNextStateID);
    CAG_State *s1 = <span class="code-keyword">new</span> CAG_State(++m_nNextStateID);

    <span class="code-comment">//</span><span class="code-comment"> Add the transition from s0-&gt;s1 on input character
</span>    s0-&gt;AddTransition(chInput, s1);

    <span class="code-comment">//</span><span class="code-comment"> Create a NFA from these 2 states 
</span>    FSA_TABLE NFATable;
    NFATable.push_back(s0);
    NFATable.push_back(s1);

    <span class="code-comment">//</span><span class="code-comment"> push it onto the operand stack
</span>    m_OperandStack.push(NFATable);

    <span class="code-comment">//</span><span class="code-comment"> Add this character to the input character set
</span>    m_InputSet.insert(chInput);
}</PRE>
<P>As we can see, the character is converted to a simple NFA and then the resulting NFA is added to the stack. <CODE>CAG_State</CODE> class is a simple class, which helps us structure the a NFA as we need it. It contains an array of transitions to other states on specific characters. Epsilon transition is transition on character 0x0. At this point, it is easy to see the structure behind NFA. An NFA (and DFA) is stored as a sequence of states (<CODE>deque</CODE> of <CODE>CAG_State</CODE> pointers). Each state is having as a member, all the transitions stored in a multimap. A transition is nothing else than mapping from a character to a state (<CODE>CAG_State*</CODE>). For detailed definition of the <CODE>CAG_State</CODE> class, please refer to the code.</P>
<P>Now back to the conversion from regular expression to NFA. Now that we know how to push the NFA onto the stack, the pop operation is trivial. Just retrieve the NFA from the stack and that's it. As I said earlier, a NFA table is defined to be a double ended queue (STL container <CODE>deque&lt;CAG_State*&gt;</CODE>). In this way, we know that the first state in the array is always the starting state, while the last state is final/accepting state. By preserving this order, we can quickly get the first and last states as well as append and prepend additional states when performing operations (like Star operator). Here is the code to evaluate each individual operation:</P><PRE>BOOL CAG_RegEx::Concat()
{
    <span class="code-comment">//</span><span class="code-comment"> Pop 2 elements
</span>    FSA_TABLE A, B;
    <span class="code-keyword">if</span>(!Pop(B) || !Pop(A))
        <span class="code-keyword">return</span> FALSE;

    <span class="code-comment">//</span><span class="code-comment"> Now evaluate AB
</span>    <span class="code-comment">//</span><span class="code-comment"> Basically take the last state from A
</span>    <span class="code-comment">//</span><span class="code-comment"> and add an epsilon transition to the
</span>    <span class="code-comment">//</span><span class="code-comment"> first state of B. Store the result into
</span>    <span class="code-comment">//</span><span class="code-comment"> new NFA_TABLE and push it onto the stack
</span>    A[A.size()-1]-&gt;AddTransition(<span class="code-digit">0</span>, B[<span class="code-digit">0</span>]);
    A.insert(A.end(), B.begin(), B.end());

    <span class="code-comment">//</span><span class="code-comment"> Push the result onto the stack
</span>    m_OperandStack.push(A);
    
    <span class="code-keyword">return</span> TRUE;
}</PRE>
<P>As we can see, the concatenation is popping two NFAs from the stack. First NFA is changed, so that it is now new NFA, which is then pushed on the stack. Note that we first pop second operand. This is the case because in regular expressions, the order of operands is of importance because AB != BA (not commutative).</P><PRE>BOOL CAG_RegEx::Star()
{
    <span class="code-comment">//</span><span class="code-comment"> Pop 1 element
</span>    FSA_TABLE A, B;
    <span class="code-keyword">if</span>(!Pop(A))
        <span class="code-keyword">return</span> FALSE;

    <span class="code-comment">//</span><span class="code-comment"> Now evaluate A*
</span>    <span class="code-comment">//</span><span class="code-comment"> Create 2 new states which will be inserted 
</span>    <span class="code-comment">//</span><span class="code-comment"> at each end of deque. Also take A and make 
</span>    <span class="code-comment">//</span><span class="code-comment"> a epsilon transition from last to the first 
</span>    <span class="code-comment">//</span><span class="code-comment"> state in the queue. Add epsilon transition 
</span>    <span class="code-comment">//</span><span class="code-comment"> between two new states so that the one inserted 
</span>    <span class="code-comment">//</span><span class="code-comment"> at the begin will be the source and the one
</span>    <span class="code-comment">//</span><span class="code-comment"> inserted at the end will be the destination
</span>    CAG_State *pStartState    = <span class="code-keyword">new</span> CAG_State(++m_nNextStateID);
    CAG_State *pEndState    = <span class="code-keyword">new</span> CAG_State(++m_nNextStateID);
    pStartState-&gt;AddTransition(<span class="code-digit">0</span>, pEndState);

    <span class="code-comment">//</span><span class="code-comment"> add epsilon transition from start state to the first state of A
</span>    pStartState-&gt;AddTransition(<span class="code-digit">0</span>, A[<span class="code-digit">0</span>]);

    <span class="code-comment">//</span><span class="code-comment"> add epsilon transition from A last state to end state
</span>    A[A.size()-1]-&gt;AddTransition(<span class="code-digit">0</span>, pEndState);

    <span class="code-comment">//</span><span class="code-comment"> From A last to A first state
</span>    A[A.size()-1]-&gt;AddTransition(<span class="code-digit">0</span>, A[<span class="code-digit">0</span>]);

    <span class="code-comment">//</span><span class="code-comment"> construct new DFA and store it onto the stack
</span>    A.push_back(pEndState);
    A.push_front(pStartState);

    <span class="code-comment">//</span><span class="code-comment"> Push the result onto the stack
</span>    m_OperandStack.push(A);

    <span class="code-keyword">return</span> TRUE;
}</PRE>
<P>Star operator pops a single element from the stack, changes it according to the Thompson's rule (see above) and then pushes it on the stack.</P><PRE>BOOL CAG_RegEx::Union()
{
    <span class="code-comment">//</span><span class="code-comment"> Pop 2 elements
</span>    FSA_TABLE A, B;
    <span class="code-keyword">if</span>(!Pop(B) || !Pop(A))
        <span class="code-keyword">return</span> FALSE;

    <span class="code-comment">//</span><span class="code-comment"> Now evaluate A|B
</span>    <span class="code-comment">//</span><span class="code-comment"> Create 2 new states, a start state and
</span>    <span class="code-comment">//</span><span class="code-comment"> a end state. Create epsilon transition from
</span>    <span class="code-comment">//</span><span class="code-comment"> start state to the start states of A and B
</span>    <span class="code-comment">//</span><span class="code-comment"> Create epsilon transition from the end 
</span>    <span class="code-comment">//</span><span class="code-comment"> states of A and B to the new end state
</span>    CAG_State *pStartState    = <span class="code-keyword">new</span> CAG_State(++m_nNextStateID);
    CAG_State *pEndState    = <span class="code-keyword">new</span> CAG_State(++m_nNextStateID);
    pStartState-&gt;AddTransition(<span class="code-digit">0</span>, A[<span class="code-digit">0</span>]);
    pStartState-&gt;AddTransition(<span class="code-digit">0</span>, B[<span class="code-digit">0</span>]);
    A[A.size()-1]-&gt;AddTransition(<span class="code-digit">0</span>, pEndState);
    B[B.size()-1]-&gt;AddTransition(<span class="code-digit">0</span>, pEndState);

    <span class="code-comment">//</span><span class="code-comment"> Create new NFA from A
</span>    B.push_back(pEndState);
    A.push_front(pStartState);
    A.insert(A.end(), B.begin(), B.end());

    <span class="code-comment">//</span><span class="code-comment"> Push the result onto the stack
</span>    m_OperandStack.push(A);

    <span class="code-keyword">return</span> TRUE;
}</PRE>
<P>Finally, the union pops two elements, makes the transformation and pushes the result on the stack. Note that here we have to watch for the order of the operation. </P>
<P>Finally, we are now able to evaluate the regular expression. If everything goes well, we will have a single NFA on the stack, which will be our resulting NFA. Here is the code, which utilizes the above functions.</P><PRE>BOOL CAG_RegEx::CreateNFA(<span class="code-keyword">string</span> strRegEx)
{
    <span class="code-comment">//</span><span class="code-comment"> Parse regular expresion using similar 
</span>    <span class="code-comment">//</span><span class="code-comment"> method to evaluate arithmetic expressions
</span>    <span class="code-comment">//</span><span class="code-comment"> But first we will detect concatenation and
</span>    <span class="code-comment">//</span><span class="code-comment"> insert char(8) at the position where 
</span>    <span class="code-comment">//</span><span class="code-comment"> concatenation needs to occur
</span>    strRegEx = ConcatExpand(strRegEx);

    <span class="code-keyword">for</span>(<span class="code-keyword">int</span> i=0; i&lt;strRegEx.size(); ++i)
    {
        <span class="code-comment">//</span><span class="code-comment"> get the charcter
</span>        <span class="code-keyword">char</span> c = strRegEx[i];
        
        <span class="code-keyword">if</span>(IsInput(c))
            Push(c);
        <span class="code-keyword">else</span> <span class="code-keyword">if</span>(m_OperatorStack.empty())
            m_OperatorStack.push(c);
        <span class="code-keyword">else</span> <span class="code-keyword">if</span>(IsLeftParanthesis(c))
            m_OperatorStack.push(c);
        <span class="code-keyword">else</span> <span class="code-keyword">if</span>(IsRightParanthesis(c))
        {
            <span class="code-comment">//</span><span class="code-comment"> Evaluate everyting in paranthesis
</span>            <span class="code-keyword">while</span>(!IsLeftParanthesis(m_OperatorStack.top()))
                <span class="code-keyword">if</span>(!Eval())
                    <span class="code-keyword">return</span> FALSE;
            <span class="code-comment">//</span><span class="code-comment"> Remove left paranthesis after the evaluation
</span>            m_OperatorStack.pop(); 
        }
        <span class="code-keyword">else</span>
        {
            <span class="code-keyword">while</span>(!m_OperatorStack.empty() &amp;&amp; Presedence(c, m_OperatorStack.top()))
                <span class="code-keyword">if</span>(!Eval())
                    <span class="code-keyword">return</span> FALSE;
            m_OperatorStack.push(c);
        }
    }

    <span class="code-comment">//</span><span class="code-comment"> Evaluate the rest of operators
</span>    <span class="code-keyword">while</span>(!m_OperatorStack.empty())
        <span class="code-keyword">if</span>(!Eval())
            <span class="code-keyword">return</span> FALSE;

    <span class="code-comment">//</span><span class="code-comment"> Pop the result from the stack
</span>    <span class="code-keyword">if</span>(!Pop(m_NFATable))
        <span class="code-keyword">return</span> FALSE;

    <span class="code-comment">//</span><span class="code-comment"> Last NFA state is always accepting state
</span>    m_NFATable[m_NFATable.size()-1]-&gt;m_bAcceptingState = TRUE;

    <span class="code-keyword">return</span> TRUE;
}</PRE>
<P>Function <CODE>Eval</CODE> is actually evaluating the next operator on the stack. Function <CODE>Eval()</CODE> pops the next operator from the operator stack, and using the <CODE><span class='cpp-keyword'>switch</span></CODE> statement, it determines which operation to use. Parenthesis are treated as operators too, because they determine the order of evaluation. The function <CODE>Presedence(<span class='cpp-keyword'>char</span> Left, <span class='cpp-keyword'>char</span> Right)</CODE> determines the precedence of two operators and returns <CODE>TRUE</CODE> if precedence of <CODE>Left</CODE> operator &lt;= precedence of <CODE>Right</CODE> operator. Please check out the code for implementation.</P>
<H2><A name=Four>Subset Construction Algorithm</A></H2>
<P>Now that we know how to convert any regular expression to an NFA, the next step is to convert NFA to DFA. At first, this process seems to be very challenging. We have a graph with zero or more Epsilon transitions, and multiple transitions on single character and we need an equivalent graph with no Epsilon transitions and a unique path for each accepted sequence of input characters. Like I said, it seems to be very challenging, but it is really not. Mathematicians actually already solved that problem for us, and then using the results, computer scientists created the Subset Construction Algorithm. I am not sure whom to give credit here but the Subset Construction Algorithm goes like this:</P>
<P>First, let us define 2 functions:</P>
<UL>
<LI><CODE>Epsilon Closure</CODE>: This function takes as a parameter, a set of states <CODE>T</CODE> and returns again a set of states containing all those states, which can be reached from each individual state of the given set <CODE>T</CODE> on Epsilon transition. 
<LI><CODE>Move</CODE>: Move takes a set of states <CODE>T</CODE> and input character <CODE>a</CODE> and returns all the states that can be reached on given input character form all states in <CODE>T</CODE>. </LI></UL>
<P>Now using these 2 functions, we can perform the transformation:</P>
<OL>
<LI>The start state of DFA is created by taking the <CODE>Epsilon closure</CODE> of the start state of the NFA 
<LI>For each new DFA state, perform the following for each input character: 
<OL type=i>
<LI>Perform <CODE>move</CODE> to the newly created state 
<LI>Create new state by taking the <CODE>Epsilon closure</CODE> of the result (i). Note that here we could get a state, which is already present in our set. This will result in a set of states, which will form the new DFA state. Note that here from one or many NFA states, we are constructing a single DFA state. </LI></OL>
<LI>For each newly created state, perform step 2. 
<LI>Accepting states of DFA are all those states, which contain at least one of the accepting states from NFA. Keep in mind that we are here constructing a single DFA state from one or many NFA states.</LI></OL>
<P>Simple enough? If not, then read further. Following is the pseudo code found on the pages 118-121 of the book "Compilers - Principles, Techniques and Tools" by Aho, Sethi and Ullman. The algorithm below is the equivalent to the algorithm above but expressed in a different way. First, let's define the <CODE>Epsilon Closure</CODE> function:</P><PRE>S EpsilonClosure(T)
{
  push all states <span class="code-keyword">in</span> T onto the stack
    initialize result to T
    <span class="code-keyword">while</span> stack is <span class="code-keyword">not</span> empty
    {
        pop t from the stack
        <span class="code-keyword">for</span> <span class="code-keyword">each</span> state u with an edge from t to u labeled epsilon
        {
            <span class="code-keyword">if</span> u is <span class="code-keyword">not</span> <span class="code-keyword">in</span> EpsilonClosure(T)
            {
                add u to result
                push u onto the stack
            }
        }
    }
    <span class="code-keyword">return</span> result
}</PRE>
<P>Basically, what this function does is, goes through all the states in <CODE>T</CODE> and checks what other states can be reached from these on no input. Note that each state can reach at least one state on no input, namely itself. Then the function goes through all these resulting states and checks for further transitions on no input. For example, let us look at the following:</P>
<P align=center><IMG height=481 src="/KB/recipes/OwnRegExpressionsParser/etrans.jpg" width=241></P>
<P>If we would call Epsilon transition on a set of states <CODE>{s0,s2}</CODE> the resulting states would be <CODE>{s0,s2,s1,s3}</CODE>. This is because from <CODE>s0</CODE>, we can reach <CODE>s1</CODE> on no input, but from <CODE>s1</CODE>, we can reach <CODE>s3</CODE> on no input, so from <CODE>s1</CODE> we can reach <CODE>s3</CODE> on no input.</P>
<P>Now that we know how the Epsilon transition works, let us look at the pseudo code to transform an NFA to a DFA: </P><PRE>D-States = EpsilonClosure(NFA Start State) and it <span class="code-keyword">is</span> unmarked
<span class="code-keyword">while</span> there are any unmarked states <span class="code-keyword">in</span> D-States
{
    mark T
    <span class="code-keyword">for</span> each input symbol a
    {
        U = EpsilonClosure(Move(T, a));
        <span class="code-keyword">if</span> U <span class="code-keyword">is</span> not <span class="code-keyword">in</span> D-States
        {
            add U <span class="code-keyword">as</span> an unmarked state to D-States
        }
        DTran[T,a] = U
    }
}</PRE>
<P>Finally the <CODE>DTran</CODE> is the DFA table, equivalent to the NFA.</P>
<P>Before we go to the next step, let us convert an NFA to a DFA by hand, using this process. If you want to master this process, I would strongly suggest that you perform more similar transformations using this method. Let's convert the following NFA to its corresponding DFA using subset construction algorithm:</P>
<P align=center><IMG height=337 src="/KB/recipes/OwnRegExpressionsParser/NFA.jpg" width=255></P>
<P>Using the subset construction algorithm, we would do following (Each newly created state will be <B>bolded</B>):</P>
<OL>
<LI>Create start state of DFA by taking epsilon closure of the start state of NFA. This step produces the set of states: <B><CODE>{s1,s2,s4}</CODE></B> 
<LI>Perform <CODE>Move('a', {s1,s2,s4})</CODE>, which results in set: <CODE>{s3,s4}</CODE> 
<LI>Perform <CODE>EpsilonTransition({s3,s4})</CODE>, which creates a new DFA state: <B><CODE>{s3,s4}</CODE></B> 
<LI>Perform <CODE>Move('b', {s1,s2,s4})</CODE>, which results in set: <CODE>{s5}</CODE> 
<LI>Perform <CODE>EpsilonTransition({s5})</CODE>, which creates new DFA state: <B><CODE>{s5}</CODE></B> 
<LI><B>Note</B>: Here we must record 2 new DFA states <CODE>{s3,s4}</CODE> and <CODE>{s5}</CODE>, together with DFA starting state <CODE>{s1,s2,s4}</CODE>. Also we must record transition on character <CODE>a</CODE> from <CODE>{s1,s2,s4}</CODE> to <CODE>{s3,s4}</CODE> and on character <CODE>b</CODE> from <CODE>{s1,s2,s4}</CODE> to <CODE>{s5}</CODE>. 
<LI>Perform <CODE>Move('a', {s3,s4})</CODE>, which returns: <CODE>{s4}</CODE> 
<LI>Perform <CODE>EpsilonTransition({s4})</CODE>, with result: <B><CODE>{s4}</CODE></B> 
<LI>Perform <CODE>Move('b', {s3,s4})</CODE>, which results in set: <CODE>{s3,s5}</CODE> 
<LI>Perform <CODE>EpsilonTransition({s3,s5})</CODE> with result: <B><CODE>{s3,s5}</CODE></B> 
<LI><B><CODE>{s3,s4}</CODE>-&gt;<CODE>{s4}</CODE> on <CODE>a</CODE></B> 
<LI><B><CODE>{s3,s4}</CODE>-&gt;<CODE>{s3,s5}</CODE> on <CODE>b</CODE></B> 
<LI>Perform <CODE>Move('a', {s5})</CODE>, which returns an empty set, so we don't need to check Epsilon transitions 
<LI>Perform <CODE>Move('b', {s5})</CODE>, which returns an empty set, so forget it. 
<LI>Perform <CODE>Move('a', {s4})</CODE>, which returns: <CODE>{s4}</CODE>. But this is <B>not</B> a new state, so forget it. However we must record the transition: 
<LI><B><CODE>{s4}</CODE>-&gt;<CODE>{s4}</CODE> on <CODE>a</CODE></B> 
<LI>Perform <CODE>Move('b', {s4})</CODE> which returns: <CODE>{s5}</CODE> 
<LI>Perform <CODE>EpsilonTransition({s5})</CODE> which returns: <CODE>{s5}</CODE> (not new, but we must record transition) 
<LI><B><CODE>{s4}</CODE>-&gt;<CODE>{s5}</CODE> on <CODE>b</CODE></B> 
<LI>Perform <CODE>Move('a', {s3,s5})</CODE> which returns an empty set, so forget it. 
<LI>Perform <CODE>Move('b', {s3,s5})</CODE> which produces: <CODE>{s3}</CODE> 
<LI><CODE>EpsilonTransition({s3})</CODE> produces: <B><CODE>{s3}</CODE></B>, <B>a NEW DFA state</B> 
<LI><B><CODE>{s3,s5}</CODE>-&gt;<CODE>{s3}</CODE> on <CODE>b</CODE></B> 
<LI><CODE>Move('a', {s3})</CODE> is an empty set 
<LI><CODE>Move('b', {s3})</CODE> is <CODE>{s3}</CODE> which is not new but transition must be recorded! 
<LI><B><CODE>{s3}</CODE>-&gt;<CODE>{s3}</CODE> on <CODE>b</CODE></B> </LI></OL>
<P>There are no new states, so we are done. Following is the drawing of the DFA:</P>
<P align=center><IMG height=617 src="/KB/recipes/OwnRegExpressionsParser/DFA.jpg" width=336></P>
<P>The starting state is <CODE>{s1,s2,s4}</CODE>, because that is <CODE>EpsilonClosure(Starting state of NFA)</CODE>. The accepting states are <CODE>{s5}</CODE>, <CODE>{s3,s4}</CODE>, and <CODE>{s3,s5}</CODE> because they contain <CODE>s3</CODE> and/or <CODE>s5</CODE>, which are accepting states of the NFA.</P>
<H2><A name=Five>DFA Optimization</A></H2>
<P>Now that we have all the knowledge to convert a regular expression into an NFA and then convert NFA to an equivalent DFA, we actually could stop at this point and use it for patterns matching. Originally when I planned to write this article, in order to keep it as simple as possible showing only principles, DFA optimization was not taken into account. But then it occurred to me that, first of all for large regular expressions, we are creating very large NFAs (by the nature of Thompson's algorithm), which in turn occasionally creates complex DFAs. If we would search for patterns, this might slow us considerably down, so I decided to include the optimization as a part of the regular expression parser. The optimization here is not a complicated one. So let's look at the following example:</P>
<P><IMG height=583 src="/KB/recipes/OwnRegExpressionsParser/DFAOptimization.jpg" width=569></P>
<P>If we look at this DFA, we notice that state <CODE><span class='cpp-literal'>3</span></CODE> is first of all not a final state. Additionally we notice that there are no outgoing edges from this state except for the loop. In other words, once we get into state <CODE><span class='cpp-literal'>3</span></CODE>, there is no chance to get to an accepting state. This is due to the fact that a DFA, besides the fact that it has a unique path for each accepting string and does not contain the Epsilon transitions, it also must have a transition on all input characters from a particular state (Here all input characters mean, the set of possibly accepting input characters. For example: <CODE>a|b|c</CODE>, the set of input characters here is <CODE>{a,b,c}</CODE>). Here is where we abuse the math a little bit, in order to make a DFA simpler. By deleting the state <CODE><span class='cpp-literal'>3</span></CODE>, our DFA becomes simpler, and it still accepts same set of patterns. In this case, our DFA is not anymore exactly a DFA. If you are asking yourself, why is this important, well the answer is: It is not! At least for us! We will use this very basic optimization mechanism to delete all the states with such characteristics and so we will obtain a smaller and compacter DFA for pattern matching. To summarize, we will delete states (and all transitions leading to these states from other states) with following characteristics:</P>
<OL>
<LI>State is not an accepting state 
<LI>State does not have any transitions to any other different state. </LI></OL>
<P>So the result is following:</P>
<P><IMG height=460 src="/KB/recipes/OwnRegExpressionsParser/DFAOptimizationOptimized.jpg" width=236></P>
<P>The DFA above, definitely seems to be smaller than the the previous one. I will still call this a DFA, despite the fact that it is not really a DFA.</P>
<H2><A name=Six>Using the results from parts above</A></H2>
<P>Finally we are ready to use all of the parts from above, to match some text patterns. Once we have the DFA, all we need to do is to take an input character and run it against the starting state. Here is the pseudo code to do that:</P><PRE>Find(string s)
{
    <span class="code-keyword">for</span> <span class="code-keyword">each</span> character c <span class="code-keyword">in</span> s
    {
        <span class="code-keyword">for</span> <span class="code-keyword">each</span> active state s
        {
            <span class="code-keyword">if</span> there is transition from s on c
            {
                go to the next state t
                <span class="code-keyword">if</span> t is accepting state
                {
                    record the pattern 
                }
                mark t as active
            }
            mark s as inactive
        }
        
        <span class="code-keyword">if</span> there is transition from starting state on c
        {
            go to the next state s
            <span class="code-keyword">if</span> s is accepting state
            {
                record the pattern
            }
            mark s as active
        }
    }
}</PRE>
<P>The code above can be found in the <CODE>Find(...)</CODE> function of the regular expression class. To keep track of active states, I use a linked list, so I can quickly add and delete states that are active/inactive respectively. After all characters are processed, all results are stored in a vector, which contains pattern matches. Using the functions <CODE>FindFirst(...)</CODE> and <CODE>FindNext(...)</CODE>, you can traverse through the results. Please refer to the documentation of the <CODE>CAG_RegEx</CODE> class for information on how to use the class. Also, at this point, I have to stress that the demo program loads the complete file into the rich edit control and then when searching is done, it stores it into a string, passing it as an argument to the <CODE>FindFirst</CODE> function. Depending on your RAM size, I would avoid loading of huge files, because it could take a lot of time to copy the data from one string to another, because of the use of virtual memory. Like I said earlier, the program is designed to show the principles behind pattern matching in text files. Depending on time, future releases might incorporate a more complete regular expression parser that searches through files of any size and delivers the results in different ways.</P>
<P>At this point, for the completeness of the article, I must note that there is a way of converting a regular expression directly into a DFA. This method is not explained here yet, but if time permits, it will be in future articles (or article updates). Additionally, there are different ways of constructing an NFA from regular expressions.</P>
<H2><A name=Seven>Final Words</A></H2>
<P>Well, that's it! I hope you enjoyed reading the article as much as I enjoyed writing it. Please use the demo code in any kind of applications, but give me the credit where deserved. If you want to build a more complete library, using the demo code presented here, please send me a copy of your additions. </P>
<P><B>Note</B>: The class <CODE>CAG_RegEx</CODE> contains two functions <CODE>SaveDFATable()</CODE> and <CODE>SaveNFATable</CODE>, which in debug mode save the NFA and DFA to <I>c:\NFATable.txt</I> and <I>c:\DFATable.txt</I> respectively. As the names already reveal, these are NFA and DFA tables. Additionally, the class has functions <CODE>SaveNFAGraph()</CODE> and <CODE>SaveDFAGraph()</CODE>, which in debug mode create 2 files <I>c:\NFAGraph.dot</I> and <I>c:\DFAGraph.dot</I>. These files are simple text files, containing the instructions for drawing these graphs using Graphviz (Check out the reference 4 below). </P>
<H2><A name=Eight>Reference</A>s &amp; Tools Used</H2>
<OL>
<LI>"Discrete Mathematics" - Richard Johnsonbaugh (Fifth Edition) 
<LI>"Discrete Mathematics and Its Applications" - Kenneth H. Rosen (Fourth Edition) 
<LI>"Compilers - Principles, Techniques and Tools" - Aho, Sethi and Ullman 
<LI>Graphviz from ATT (Tool for drawing of any kind of graphs). You can find it <A href="http://www.research.att.com/sw/tools/graphviz/" target=_blank>here</A>. </LI></OL>


						</div>
						

						
						
						<h2>License</h2>
						<div id="LicenseTerms"><p>This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.</p><p>A list of licenses authors might use can be found <a href="/info/Licenses.aspx">here</a></p></div>
						

						<div class="float-right" style="margin:20px 0 0 0;border:1px solid #ccc">
						<div class="msg-300x250" data-format="300x250" data-type="ad" data-publisher="lqm.codeproject.site" data-zone="ros"  data-loadOnView='true'  data-tags='VC6, VC7, VC7.1, Win2K, WinXP, Win2003, STL, Dev, Beginner,rating4.5'></div>
						</div>

						
						<h2 id="ctl00_AboutHeading">About the Author</h2>
						

<div class="container">
<div style="width:210px;overflow:hidden;float:left;text-align:center">
	<img id="ctl00_AboutAuthorRptr_ctl00_AboutAuthor_memberPhoto" class="profile-pic" src="http://www.codeproject.com/script/Membership/ProfileImages/{426BE88A-E6C4-4EEA-9644-ABC5CF0B1655}.gif" style="border-width:0px;transform:rotate(2deg);" />
</div>
<div class="container-member float-left" style="width:235px">
	<b><a id="ctl00_AboutAuthorRptr_ctl00_AboutAuthor_memberProfileLink" class="author" href="/Members/Amer-Gerzic">Amer Gerzic</a></b>
	<div class="company">
		<span id="ctl00_AboutAuthorRptr_ctl00_AboutAuthor_memberJobTitle">President</span>
		<span id="ctl00_AboutAuthorRptr_ctl00_AboutAuthor_memberCompany">Infinity Software Solutions, LLC.</span> 
		<br /><span id="ctl00_AboutAuthorRptr_ctl00_AboutAuthor_memberLocation">United States <img src="/script/Geo/Images/US.gif" alt="United States" width="16px" height="11px" /></span>
	</div>
</div>
	
<div class="padded-top float-left clearfix" style="width:600px">
	Originally from Bosnia and Herzegovina, but lived for 6 years in Germany where I did majority of education, then moved to US, where I live since 1999. I like programming, computers in general, but also Basketball, Soccer, Tennis, and many other things. Masters graduate from Grand Valley State University in CIS and working as a full time software developer. Please visit my website <a rel="nofollow" href="http://www.amergerzic.com">www.amergerzic.com</a>

	

	
</div>
</div><br />
						
						

						<div class="clearfix"></div>

						<div style="padding-top:8px">
							<a class="anchorLink" href="/Articles/5412/Writing-own-regular-expression-parser#_articleTop">Article Top</a>
						</div>

						
						<div style="margin:auto;height:90px;margin-top:10px" class="sticky-stop"> 
							<div class="msg-728x90" data-format="728x90" data-type="ad" data-publisher="lqm.codeproject.site" data-zone="bottom"  data-loadOnView='true'  data-tags='VC6, VC7, VC7.1, Win2K, WinXP, Win2003, STL, Dev, Beginner,pos_bottom'></div>
						</div>
						
					

				    
					</form>

				</div>

				
				

					<h2>Comments and Discussions</h2>
					<a class="float-left" name="_comments" id="_comments">&nbsp;</a><div id="_MessageBoardctl00_MessageBoard" onclick="return SwitchMessage(event, null)">
	<table id="ForumTable" class="forum relaxed" cellpadding="0" cellspacing="0">
		<tr>
			<td class="header1 callout"><b>You must <a href="https://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser%3ffid%3d26032%26df%3d90%26mpp%3d25%26noise%3d3%26prof%3dFalse%26sort%3dPosition%26view%3dNormal%26spc%3dRelaxed">Sign In</a> to use this message board.</b></td>
		</tr><tr>
			<td><table width="100%" border="0" cellpadding="3px" cellspacing="0">
				<tr class="header1">
					<td colspan="2" style="white-space:nowrap;"><div class="container">
						<div class="float-right">
							<form action="/Search.aspx?fid=0" method="get" class="searchbar">
								<input type="hidden" name="fid" value="26032" /><b>Search this forum </b><input type="search" class="search" name="qf" />&nbsp;<input type="submit" value="Go" class="button" />
							</form>
						</div>
					</div></td><tr class="header2">
						<td></td><td style="width:100%;"><div style="text-align:right;">
							<form action="/script/Forums/SetOptions.aspx?floc=%2fArticles%2f5412%2fWriting-own-regular-expression-parser&amp;fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed" method="get" style="margin:0;padding:0;">
								<input type="hidden" name="fid" value="26032" /><input type="hidden" name="currentQS" value="?floc=%2fArticles%2f5412%2fWriting-own-regular-expression-parser&amp;fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed" /><input type="hidden" name="floc" value="/Articles/5412/Writing-own-regular-expression-parser" /><input type="checkbox" name="prof" id="prof" style="vertical-align:middle;" /><label for="prof">Profile popups</label>&nbsp;&nbsp;&nbsp;&nbsp;Spacing<select size="1" class="dropdown" name="spc">
									<option selected value="Relaxed">Relaxed</option><option value="Compact">Compact</option><option value="Tight">Tight</option>
								</select>&nbsp;&nbsp;Noise<select size="1" class="dropdown" name="noise">
									<option value="1">Very High</option><option value="2">High</option><option selected value="3">Medium</option><option value="4">Low</option><option value="5">Very Low</option>
								</select>&nbsp;&nbsp;Layout<select size="1" class="dropdown" name="view">
									<option value="Normal">Normal</option><option value="Topic">Open Topics</option><option selected value="Expanded">Open All</option><option value="Thread">Thread View</option>
								</select>&nbsp;&nbsp;Per page<select size="1" class="dropdown" name="mpp">
									<option value="10">10</option><option selected value="25">25</option><option value="50">50</option>
								</select>&nbsp;&nbsp;&nbsp;<input type="submit" value="Update" name="SetOpt" class="button" />
							</form>
						</div></td>
					</tr>
				</tr>
			</table></td><tr>
				<td><a name="xx0xx"></a><table border="0" cellpadding="2px" cellspacing="0" width="100%">
					<tr class="navbar">
						<td></td><td style="text-align:right;width:50%;"></td><td style="text-align:right;white-space:nowrap;"><span class="nav-link disabled">First</span> <span class="nav-link disabled">Prev</span><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=26#xx0xx">Next</a></td>
					</tr>
				</table></td>
			</tr><tr>
				<td><table border="0" cellpadding="0" cellspacing="0" width="100%" class="fixed-layout blank-background">
					<tr>
						<td><img src="http://s.codeproject.com/script/Forums/Images/t.gif" border="0" width="1px" height="5px" alt="" /></td>
					</tr><tr id="F4656617_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx4656617xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_question.gif" alt="Question" /></td><td class="subject hover-container">Lots of thanks..</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=10255374">Member 10255374</a></td><td class="date">10-Sep-13  5:16&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="10255374" msgid="4656617" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Hi Amer,<br />
I have read your complete article and that have helped me a lot to understand regular expressions. I am working to design an automata from regular expression and then carrying out respective parse tree generation. May I request for your java code? I hope that could help me in my project.My email id is - shruti.101291@gmail.com<br />
&nbsp;<br />
Thanks for making such good article in so understandable language.<br />
Keep the good work going..<img src="/script/Forums/Images/thumbs_up.gif" align="top" alt="Thumbs Up | :thumbsup:" /> <br />
Shruti<br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=4656617" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/4656617/Lots-of-thanks.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF4656617" data-ref="3_4656617" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F4447807_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx4447807xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_question.gif" alt="Question" /></td><td class="subject hover-container">Errors in the Thompson's Algorithm [modified]</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=9669945">mnicky</a></td><td class="date">9-Dec-12  4:27&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="9669945" msgid="4447807" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">I think that you have few errors in the Thompson's algorithm (its <a href="http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser/Thompson.jpg">image</a>[<a href="http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser/Thompson.jpg" target="_blank" title="New Window">^</a>]). The intermediate states in the concatenation, union and Kleene-closure NFAs shouldn't be marked as final (accepting). Only the last state of those NFAs should be final. See also e.g. <a href="http://en.wikipedia.org/wiki/Thompson's_construction_algorithm">article about Thompson's algorithm on Wikipedia</a>[<a href="http://en.wikipedia.org/wiki/Thompson's_construction_algorithm" target="_blank" title="New Window">^</a>].<br /><br /><div class="modified">modified  9-Dec-12 10:46am.</div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=4447807" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/4447807/Errors-in-the-Thompsons-Algorithm.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF4447807" data-ref="3_4447807" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F4447906_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="38px" class="indent"><a name="xx4447906xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_answer.gif" alt="Answer" /></td><td class="subject hover-container"><a class="message-link" name="4447906" parent="4447807" thread="4447807" href="/Messages/4447906/Re-Errors-in-the-Thompsons-Algorithm.aspx">Re: Errors in the Thompson's Algorithm</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">9-Dec-12  9:59&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:38px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="38px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="4447906" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Hi,<br />
Yes, that is correct. However, it was simply copy and paste to demonstrate concatenation of basic elements ... tried to make it easier to recognize.<br />
&nbsp;<br />
Code implementation is obviously not marking those states as final.<br />
&nbsp;<br />
Thanks<br />
Amer<br />
<div class="signature">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=4447807" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/4447906/Re-Errors-in-the-Thompsons-Algorithm.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF4447906" data-ref="3_4447906" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F4445335_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx4445335xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_question.gif" alt="Question" /></td><td class="subject hover-container">Counting</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=9660429">Kuzayfa</a></td><td class="date">5-Dec-12  20:33&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="9660429" msgid="4445335" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Thank you very much. This was very valuable information for me, since I am going to solve one puzzle related to reg. expressions. Before digging into your implementation deeply I wanted to ask you one thing. Is it possible to count the over all number of strings/patterns the dfa can match if we know that such strings are finite. If it is possible or not so much difficult to modify in your code in order to do this please give the idea, because I really need it<br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=4445335" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/4445335/Counting.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF4445335" data-ref="3_4445335" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F4445582_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="38px" class="indent"><a name="xx4445582xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_answer.gif" alt="Answer" /></td><td class="subject hover-container"><a class="message-link" name="4445582" parent="4445335" thread="4445335" href="/Messages/4445582/Re-Counting.aspx">Re: Counting</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">6-Dec-12  2:10&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:38px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="38px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="4445582" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Hi,<br />
&nbsp;<br />
Yes, it is possible to count all matches (shortest to longest), simply by increasing the counter when ever you reach a finishing state. Once you reach finishing state, you can simply go and continue matching until you either run out of characters or end up in "dead ends" ...<br />
&nbsp;<br />
Thanks<br />
Amer<br />
<div class="signature">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=4445335" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/4445582/Re-Counting.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF4445582" data-ref="3_4445582" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F3801907_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx3801907xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container">Awesome</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=3821006">Aaron_Redmond</a></td><td class="date">9-Mar-11  7:10&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="3821006" msgid="3801907" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Great code, thank a million<br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=3801907" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/3801907/Awesome.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF3801907" data-ref="3_3801907" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F3991309_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="38px" class="indent"><a name="xx3991309xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="3991309" parent="3801907" thread="3801907" href="/Messages/3991309/Re-Awesome.aspx">Re: Awesome</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">12-Aug-11  4:07&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:38px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="38px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="3991309" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">You are welcome!<br />
<div class="signature">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=3801907" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/3991309/Re-Awesome.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF3991309" data-ref="3_3991309" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F3743481_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx3743481xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container">My vote of 1</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=679772">mbue</a></td><td class="date">21-Jan-11  4:32&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="679772" msgid="3743481" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">useless code<br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=3743481" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/3743481/My-vote-of.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF3743481" data-ref="3_3743481" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F3743479_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx3743479xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container">Bad code</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=679772">mbue</a></td><td class="date">21-Jan-11  4:31&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="679772" msgid="3743479" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">too much compiler errors!<br />once compiled crashes every time. most members not initialized.<br />regex results == ZERO.<br />a lot of text (eplanations) but code is useless!<br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=3743479" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/3743479/Bad-code.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF3743479" data-ref="3_3743479" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F3167989_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx3167989xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container">Algorithm for comparing regular expressions</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=240346">SonOfPirate</a></td><td class="date">20-Aug-09  11:41&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="240346" msgid="3167989" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">I was very impressed with your knowledge of regular expression internals and wondered if you might be able to help me learn how we can compare regular expression patterns to determine if one regular expression is a subset of another or if they are equivalent.  For instance, the pattern "a*" is a subset of ".*".  Any direction, resources or insights would be appreciated.<br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=3167989" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/3167989/Algorithm-for-comparing-regular-expressions.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF3167989" data-ref="3_3167989" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F3168785_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="38px" class="indent"><a name="xx3168785xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="3168785" parent="3167989" thread="3167989" href="/Messages/3168785/Re-Algorithm-for-comparing-regular-expressions.aspx">Re: Algorithm for comparing regular expressions</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">21-Aug-09  2:21&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:38px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="38px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="3168785" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Thanks!<br />
That sounds like interesting (and very complex) problem. I never ran into that poblem and therefore do not have any resources to offer. My initial thought is to find out if a regular expression string is a "part" of another regular expression string. I would do that by comparing parse trees of regular expression strings and then look for matching subtrees. If you find subtrees, then you can look into character subsets like "." is superset of any other character expression etc.  <br />
&nbsp;<br />
Hope this helps!<br />
Amer <br />
&nbsp;<br />
<div class="ForumSig">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=3167989" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/3168785/Re-Algorithm-for-comparing-regular-expressions.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF3168785" data-ref="3_3168785" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2945988_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx2945988xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container">Thanks so much</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=4574718">langtugacon</a></td><td class="date">2-Mar-09  5:19&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="4574718" msgid="2945988" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Great tutorial! <br />
Can I translate this article into Vietnamese? We are doing an excercise about compiler, and I feel this is an good article which is very easy to understand.<br />
Thanks again ^^<br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2945988" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2945988/Thanks-so-much.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2945988" data-ref="3_2945988" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2946014_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="38px" class="indent"><a name="xx2946014xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="2946014" parent="2945988" thread="2945988" href="/Messages/2946014/Re-Thanks-so-much.aspx">Re: Thanks so much</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">2-Mar-09  5:32&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:38px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="38px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="2946014" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Yes, not a problem ... use it as you wish.<br />
Glad I could help! <br />
&nbsp;<br />
<div class="ForumSig">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2945988" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2946014/Re-Thanks-so-much.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2946014" data-ref="3_2946014" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2946033_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="38px" class="indent"><a name="xx2946033xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="2946033" parent="2945988" thread="2945988" href="/Messages/2946033/Re-Thanks-so-much.aspx">Re: Thanks so much</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">2-Mar-09  5:43&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:38px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="38px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="2946033" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Also, I did design a compiler, which can be found at http://www.amergerzic.com/post/TinyPascal.aspx. That article might be more helpful.<br />
&nbsp;<br />
Thanks <br />
&nbsp;<br />
<div class="ForumSig">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2945988" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2946033/Re-Thanks-so-much.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2946033" data-ref="3_2946033" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2664941_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx2664941xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container">C# implementation</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=1905946">Mizan Rahman</a></td><td class="date">5-Aug-08  2:20&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="1905946" msgid="2664941" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Hi,<br />
&nbsp;<br />
I have posted an article "An implemenation of regurlar expression in C#" in code project at <a href="http://www.codeproject.com/KB/recipes/re_expression_parser.aspx">http://www.codeproject.com/KB/recipes/re_expression_parser.aspx</a>[<a href="http://www.codeproject.com/KB/recipes/re_expression_parser.aspx" target="_blank" title="New Window">^</a>] <img src="/script/Forums/Images/smiley_smile.gif" align="top" alt="Smile | :)" />  <br />
&nbsp;<br />
<br />
Thanks,<br />
Mizan<br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2664941" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2664941/Csharp-implementation.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2664941" data-ref="3_2664941" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2664960_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="38px" class="indent"><a name="xx2664960xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="2664960" parent="2664941" thread="2664941" href="/Messages/2664960/Re-Csharp-implementation.aspx">Re: C# implementation</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">5-Aug-08  2:34&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:38px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="38px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="2664960" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Looks good, Thanks! <br />
&nbsp;<br />
<div class="ForumSig">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2664941" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2664960/Re-Csharp-implementation.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2664960" data-ref="3_2664960" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2648352_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx2648352xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container">C# porting [modified]</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=3504268">Ugo Moschini</a></td><td class="date">22-Jul-08  21:02&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="3504268" msgid="2648352" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Hi,<br />
here's the link to the website <a href="http://www.ugomoschini.altervista.org/regexparser.html"> www.ugomoschini.altervista.org/regexparser.html </a>  <br />
&nbsp;<br />
Ugo Moschini    <img src="/script/Forums/Images/smiley_laugh.gif" align="top" alt="Laugh | :laugh:" />  <br />
&nbsp;<br />
<div class="ForumMod">modified on Wednesday, August 20, 2008 12:17 PM</div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2648352" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2648352/Csharp-porting-modified.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2648352" data-ref="3_2648352" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2648993_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="38px" class="indent"><a name="xx2648993xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="2648993" parent="2648352" thread="2648352" href="/Messages/2648993/Re-Csharp-porting.aspx">Re: C# porting</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">23-Jul-08  4:00&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:38px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="38px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="2648993" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Hm... no reference to original work? <br />
&nbsp;<br />
<div class="ForumSig">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2648352" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2648993/Re-Csharp-porting.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2648993" data-ref="3_2648993" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2646879_h0" class="header hover-row root">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="20px" class="indent"><a name="xx2646879xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container">C# Porting [modified]</td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=3504268">Ugo Moschini</a></td><td class="date">21-Jul-08  21:41&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content root">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:20px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="20px" alt="" /><div class="voteform vertical" ownerid="3504268" msgid="2646879" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Hello, few months ago I did something like a C# porting of this regular expression parser.<br />
You can find it at www.ugomoschini.altervista.org in the 'Computer Science' section.<br />
Cheers,   <img src="/script/Forums/Images/smiley_smile.gif" align="top" alt="Smile | :)" /> <br />
&nbsp;<br />
Ugo Moschini <br />
&nbsp;<br />
<div class="ForumMod">modified on Wednesday, August 20, 2008 12:17 PM</div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2646879" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2646879/Csharp-Porting-modified.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2646879" data-ref="3_2646879" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2648994_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="38px" class="indent"><a name="xx2648994xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="2648994" parent="2646879" thread="2646879" href="/Messages/2648994/Re-Csharp-Porting.aspx">Re: C# Porting</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">23-Jul-08  4:00&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:38px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="38px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="2648994" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Hm.. no reference to original work? <br />
&nbsp;<br />
<div class="ForumSig">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2646879" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2648994/Re-Csharp-Porting.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2648994" data-ref="3_2648994" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2649278_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="56px" class="indent"><a name="xx2649278xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="2649278" parent="2648994" thread="2646879" href="/Messages/2649278/Re-Csharp-Porting.aspx">Re: C# Porting</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=3504268">Ugomos</a></td><td class="date">23-Jul-08  7:03&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:56px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="56px" alt="" /><div class="voteform vertical" ownerid="3504268" msgid="2649278" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">No reference? I beg your pardon if you think I was unkindly.. In the post, I wrote that my parser is a sort of C# porting of YOUR parser and on my website, you are the first link in REFERENCES section.<br />
Feel free to say to me any other reference you desire to your work. It's only right! Bye!<br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2646879" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2649278/Re-Csharp-Porting.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2649278" data-ref="3_2649278" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2649287_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="74px" class="indent"><a name="xx2649287xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="2649287" parent="2649278" thread="2646879" href="/Messages/2649287/Re-Csharp-Porting.aspx">Re: C# Porting</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">23-Jul-08  7:08&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:74px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="74px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="2649287" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Sorry for misunderstanding ... I was actually joking! <br />
Now that I read my own email I can see how this could happen ...<br />
&nbsp;<br />
Thanks <br />
&nbsp;<br />
<div class="ForumSig">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2646879" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2649287/Re-Csharp-Porting.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2649287" data-ref="3_2649287" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2649313_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="92px" class="indent"><a name="xx2649313xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="2649313" parent="2649287" thread="2646879" href="/Messages/2649313/Re-Csharp-Porting.aspx">Re: C# Porting</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=3504268">Ugomos</a></td><td class="date">23-Jul-08  7:26&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:92px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="92px" alt="" /><div class="voteform vertical" ownerid="3504268" msgid="2649313" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2"><img src="/script/Forums/Images/smiley_biggrin.gif" align="top" alt="Big Grin | :-D" /> <br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2646879" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2649313/Re-Csharp-Porting.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2649313" data-ref="3_2649313" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2649320_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="110px" class="indent"><a name="xx2649320xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="2649320" parent="2649313" thread="2646879" href="/Messages/2649320/Re-Csharp-Porting.aspx">Re: C# Porting</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=30261">Amer Gerzic</a></td><td class="date">23-Jul-08  7:31&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:110px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="110px" alt="" /><div class="voteform vertical" ownerid="30261" msgid="2649320" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">Hey, some people asked me about C# port. Do you mind if I link them to your page?<br />
&nbsp;<br />
Thanks <br />
&nbsp;<br />
<div class="ForumSig">Have a good one!<br />
Amer Gerzic<br />
<a href="http://www.amergerzic.com">www.amergerzic.com</a></div><br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2646879" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2649320/Re-Csharp-Porting.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2649320" data-ref="3_2649320" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr id="F2649343_h0" class="header hover-row">
						<td class="subject-line expanded " width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr>
								<td width="120px" class="indent"><a name="xx2649343xx"></a><img height="16px" width="16px" align="top" src="/script/Forums/Images/msg_general.gif" alt="General" /></td><td class="subject hover-container"><a class="message-link" name="2649343" parent="2649320" thread="2646879" href="/Messages/2649343/Re-Csharp-Porting.aspx">Re: C# Porting</a></td><td class="icon"><img border="0" src="http://s.codeproject.com/App_Themes/CodeProject/Img/icn-member-16.gif" title="member" alt="member" height="16px" /></td><td class="author"><a href="/script/Membership/View.aspx?mid=3504268">Ugomos</a></td><td class="date">23-Jul-08  7:55&nbsp;</td>
							</tr>
						</table></td>
					</tr><tr class="content">
						<td class="expanded" width="100%"><table border="0" cellpadding="0" cellspacing="0" width="100%">
							<tr valign="top">
								<td class="indent align-right" style="width:120px;"><img src="http://s.codeproject.com/script/Forums/Images/t.gif" height="1px" width="120px" alt="" /><div class="voteform vertical" ownerid="3504268" msgid="2649343" votingType="GoodOrBad">

								</div></td><td class="text"><table border="0" cellpadding="0" cellspacing="5px" width="100%">
									<tr>
										<td><table border="0" cellpadding="0" cellspacing="0" width="100%">
											<tr>
												<td colspan="2">No no, you can link everyone you want!  <img src="/script/Forums/Images/smiley_smile.gif" align="top" alt="Smile | :)" /> <br /></td>
											</tr><tr class="footer" style="vertical-align:top;">
												<td><a href="http://www.codeproject.com/script/Membership/LogOn.aspx?rp=%2fArticles%2f5412%2fWriting-own-regular-expression-parser">Sign In</a>·<wbr><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;sort=Position&amp;spc=Relaxed&amp;tid=2646879" title="View&nbsp;Thread">View&nbsp;Thread</a>·<wbr><a href="/Messages/2649343/Re-Csharp-Porting.aspx" title="Get permanent link">Permalink</a></td><td style="text-align:right;"><span id="MVF2649343" data-ref="3_2649343" class="rating-label" style="white-space:nowrap;"></span></td>
											</tr>
										</table></td>
									</tr>
								</table></td>
							</tr>
						</table></td>
					</tr><tr>
						<td><img src="http://s.codeproject.com/script/Forums/Images/t.gif" border="0" width="1px" height="5px" alt="" /></td>
					</tr>
				</table></td>
			</tr><tr>
				<td><table width="100%" cellpadding="2px" cellspacing="0">
					<tr class="footer">
						<td>Last Visit: 31-Dec-99  18:00 &nbsp; &nbsp; Last Update: 2-Apr-14  17:40</td><td><a href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed">Refresh</a></td><td style="text-align:right;white-space:nowrap;"><input id="_mbnUrl" type="hidden" value="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=26" /><span class="nav-link selected">1</span><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=26#xx0xx">2</a><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=51#xx0xx">3</a><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=76#xx0xx">4</a><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=101#xx0xx">5</a><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=126#xx0xx">6</a><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=151#xx0xx">7</a><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=176#xx0xx">8</a><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=201#xx0xx">9</a><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=226#xx0xx">10</a><a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=251#xx0xx">11</a> <a class="nav-link" name="Frm_HoverNL" href="/Articles/5412/Writing-own-regular-expression-parser?fid=26032&amp;df=90&amp;mpp=25&amp;noise=3&amp;prof=False&amp;sort=Position&amp;view=Normal&amp;spc=Relaxed&amp;fr=26#xx0xx">Next »</a></td>
					</tr>
				</table></td>
			</tr>
		</tr>
	</table><p class="small-text"><img align="top" src="/script/Forums/Images/msg_general.gif" width="16px" height="16px" alt="General" /> General &nbsp;&nbsp; <img align="top" src="/script/Forums/Images/msg_news.gif" width="16px" height="16px" alt="News" /> News &nbsp;&nbsp; <img align="top" src="/script/Forums/Images/msg_idea.gif" width="16px" height="16px" alt="Suggestion" /> Suggestion &nbsp;&nbsp; <img align="top" src="/script/Forums/Images/msg_question.gif" width="16px" height="16px" alt="Question" /> Question &nbsp;&nbsp; <img align="top" src="/script/Forums/Images/msg_bug.gif" width="16px" height="16px" alt="Bug" /> Bug &nbsp;&nbsp; <img align="top" src="/script/Forums/Images/msg_answer.gif" width="16px" height="16px" alt="Answer" /> Answer &nbsp;&nbsp; <img align="top" src="/script/Forums/Images/msg_joke.gif" width="16px" height="16px" alt="Joke" /> Joke &nbsp;&nbsp; <img align="top" src="/script/Forums/Images/msg_rant.gif" width="16px" height="16px" alt="Rant" /> Rant &nbsp;&nbsp; <img align="top" src="/script/Forums/Images/msg_admin.gif" width="16px" height="16px" alt="Admin" /> Admin &nbsp;&nbsp; </p>
				

			</div>
			
		</td>
		<td>
			<div id="ctl00_RightSideBar" class="container-article-info">

				<div class="header">About Article</div>
				<div class="article-summary">

					
					

					
					

					
					<div class="summary"><span id="ctl00_ArticleDescr">Explains principles behind writing regular expression parsers.</span></div>

					<a id="ctl00_InfoBox_ParentLink"></a>

<table cellpadding="0" cellspacing="0" class="article-info">

	
	<tr><td>Type&nbsp;</td><td class="value"><a id="ctl00_InfoBox_TypeName" href="/script/Articles/Types.aspx?#Article">Article</a></td></tr>
	

	<tr><td>Licence&nbsp;</td><td class="value"></td></tr>

	

	<tr><td>First Posted&nbsp;</td><td nowrap="nowrap" class="value"><span itemprop="datePublished" content="2003-11-10">9 Nov 2003</span></td></tr>

	<tr><td>Views&nbsp;</td><td class="value">527,051</td></tr>

		

	
	<tr><td>Bookmarked&nbsp;</td><td class="value">222 times</td></tr>
	

	

	
	
	
	<tr><td colspan="2"></td>
	</tr>
	
	
</table>

					<div class="tags"> 
					<span id="ctl00_TagsList_TagWrp" class="tags">
	
	
	
	<span id="ctl00_TagsList_VisibleTags"><span class="t"><a rel="tag" href="/Tags/VC6">VC6</a></span><span class="t"><a rel="tag" href="/Tags/VC7">VC7</a></span><span class="t"><a rel="tag" href="/Tags/VC7.1">VC7.1</a></span><span class="t"><a rel="tag" href="/Tags/Win2K">Win2K</a></span><br><span class="t"><a rel="tag" href="/Tags/WinXP">WinXP</a></span><span class="t"><a rel="tag" href="/Tags/Win2003">Win2003</a></span><span class="t"><a rel="tag" href="/Tags/STL">STL</a></span><span class="t"><a rel="tag" href="/Tags/Dev">Dev</a></span></span><acronym id="ctl00_TagsList_HiddenTags" title="plus: Beginner">, +</acronym> 

	
	
</span>

					</div>

					<div class="nowrap align-left">
						 

<a id="ctl00_ActionLinks_PrintLnk" href="/Articles/5412/Writing-own-regular-expression-parser?display=Print">
	<img src="http://s.codeproject.com/App_Themes/CodeProject/Img/print.gif" 
		width="46px" height="46px" style="border:0">
</a>

<a id="ctl00_ActionLinks_MailLink" href="/script/common/TellFriend.aspx?obtid=2&amp;obid=5412">
	<img src="http://s.codeproject.com/App_Themes/CodeProject/Img/email.gif" 
		width="46px" height="46px" style="border:0">
</a>
					</div>

					
				</div>

				<div style="width:160px;margin: 10px auto;">
					<div class="msg-160x600" data-format="160x600" data-type="ad" data-publisher="lqm.codeproject.site" data-zone="ros"  data-tags='VC6, VC7, VC7.1, Win2K, WinXP, Win2003, STL, Dev, Beginner,rating4.5'></div>
				</div>

				
<div class="padded-top">
<div class="header">Top News</div>

<p><a id="ctl00_News_News_ctl01_Link" href="http://blogs.technet.com/b/microsoft_blog/archive/2014/03/25/microsoft-makes-source-code-for-ms-dos-and-word-for-windows-available-to-public.aspx">Microsoft makes source code for MS-DOS and Word for Windows available to public</a></p>

Get the <a id="ctl00_News_News_ctl02_Subscribe" href="/Feature/Insider/">Insider News</a> free each morning.
</div>

				

				<div class="padded-top">
					
	<div id="ctl00_RelatedVideos_RelatedResults_ctl00_header" class="header">Related Videos</div>
	<div class="content-list align-center">	
	
	<div class="content-list-item">
		<a id="ctl00_RelatedVideos_RelatedResults_ctl01_Link" class="title" href="http://codeproject.tv/video/4889539/where_to_put_javascript"><img id="ctl00_RelatedVideos_RelatedResults_ctl01_Thumbnail" src="//codeprojecttv.s3.amazonaws.com/thumbnails_production/4/1241/thumb/JS-Thumbnail.png" style="border-style:None;width:125px;border-width:0px;" /></a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedVideos_RelatedResults_ctl02_Link" class="title" href="http://codeproject.tv/video/5001188/javascript_switch_statement"><img id="ctl00_RelatedVideos_RelatedResults_ctl02_Thumbnail" src="//codeprojecttv.s3.amazonaws.com/thumbnails_production/5/6061/thumb/cptv100x80ms.jpg" style="border-style:None;width:125px;border-width:0px;" /></a>
		
	</div>
	
	</div>
	

				</div>
				<div class="padded-top">
					
	<div id="ctl00_RelatedArticles_RelatedResults_ctl00_header" class="header">Related Articles</div>
	<div class="content-list">	
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl02_Link" class="title" href="/Articles/677580/Combined-Regular-Expression-Search">Combined Regular Expression Search</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl03_Link" class="title" href="/Articles/28307/An-Implementation-of-Regular-Expression-Parser-in">An Implementation of Regular Expression Parser in C#</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl04_Link" class="title" href="/Articles/125698/Approximate-String-Matching-Row-wise-Bit-paralleli">Approximate String Matching - Row-wise Bit-parallelism Algorithm (BPR)</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl05_Link" class="title" href="/Articles/4121/Generic-DFA-State-Machine-for-NET">Generic DFA State Machine for .NET</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl06_Link" class="title" href="/Articles/1695/Creating-a-pop-under-window">Creating a pop-under window</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl07_Link" class="title" href="/Articles/386890/String-Manipulation-in-the-NET-Micro-Framework">String Manipulation in the .NET Micro Framework</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl08_Link" class="title" href="/Tips/106180/UNION-ALL-between-Two-CTEs">UNION ALL between Two CTEs</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl09_Link" class="title" href="/Articles/21402/Flyout-A-great-way-to-save-space-on-your-webpage">Flyout - A great way to save space on your webpage</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl10_Link" class="title" href="/Articles/26299/How-to-make-Google-Map-Tooltip-with-Flyout">How to make Google Map Tooltip with Flyout</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl11_Link" class="title" href="/Articles/21894/TwoColorsMenu-The-fastest-menu-in-the-world">TwoColorsMenu - The fastest menu in the world</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl12_Link" class="title" href="/Tips/310145/How-to-Log-Javascript-Errors-in-Csharp">How to Log Javascript Errors in C#</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl13_Link" class="title" href="/Articles/18921/Using-Visual-Studio-to-Debug-JavaScript-in-IE">Using Visual Studio to Debug JavaScript in IE</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl14_Link" class="title" href="/Articles/333596/What-devs-should-know-about-Javascript">What you should know about if you are new to Javascript</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl15_Link" class="title" href="/Articles/23831/Detect-if-JavaScript-is-enabled-in-ASPX">Detect if JavaScript is enabled in ASPX</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl16_Link" class="title" href="/Tips/221260/Embedding-Javascript-in-Asp-Net">Embedding Javascript in Asp.Net</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl17_Link" class="title" href="/Articles/196727/Managing-Your-JavaScript-Library-in-ASP-NET">Managing Your JavaScript Library in ASP.NET</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl18_Link" class="title" href="/Tips/196535/Javascript-Injection-at-it-s-Finest-without-even-u">Javascript Injection at it's Finest!, without even using Eval()!</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl19_Link" class="title" href="/Tips/292642/Solitaire-Card-Effect">Solitaire Card Effect</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl20_Link" class="title" href="/Articles/5608/Writing-Object-Oriented-JavaScript-Part">Writing Object-Oriented JavaScript  Part 1</a>
		
	</div>
	
	<div class="content-list-item">
		<a id="ctl00_RelatedArticles_RelatedResults_ctl21_Link" class="title" href="/Articles/667138/Javascript">Javascript</a>
		
	</div>
	
	</div>
	

				</div>
				<div class="padded-top">
					
	<div id="ctl00_RelatedLibrary_RelatedResults_ctl00_header" class="header">Related Research</div>
	<div class="content-list align-center">	
	
	<div class="content-list-item">
		<div><img id="ctl00_RelatedLibrary_RelatedResults_ctl01_Thumb" class="shadow" src="/script/ResearchLibrary/Logos/in-the-wild-testing.png" style="border-width:0px;" /></div>
		<a id="ctl00_RelatedLibrary_RelatedResults_ctl01_Link" class="title" href="/ResearchLibrary/18/In-The-Wild-Testing-How-to-Ensure-Your-Apps-Work-i">In-The-Wild Testing: How to Ensure Your Apps Work in the Real World</a>
		
	</div>
	
	<div class="content-list-item">
		<div><img id="ctl00_RelatedLibrary_RelatedResults_ctl02_Thumb" class="shadow" src="/script/ResearchLibrary/Logos/LibraryItemThumbnail_31_100x129.png" style="border-width:0px;" /></div>
		<a id="ctl00_RelatedLibrary_RelatedResults_ctl02_Link" class="title" href="/ResearchLibrary/31/Protecting-Android-Applications-with-Secure-Code-S">Protecting Android™ Applications with Secure Code Signing Certificates</a>
		
	</div>
	
	<div class="content-list-item">
		<div><img id="ctl00_RelatedLibrary_RelatedResults_ctl03_Thumb" class="shadow" src="/script/ResearchLibrary/Logos/agile-software-testing.png" style="border-width:0px;" /></div>
		<a id="ctl00_RelatedLibrary_RelatedResults_ctl03_Link" class="title" href="/ResearchLibrary/20/Learn-Agile-Ten-Tips-for-Launching-and-Testing-Hig">Learn Agile: Ten Tips for Launching and Testing High Quality Apps for the American Market</a>
		
	</div>
	
	<div class="content-list-item">
		<div><img id="ctl00_RelatedLibrary_RelatedResults_ctl04_Thumb" class="shadow" src="/script/ResearchLibrary/Logos/LibraryItemThumbnail_40_100x116.png" style="border-width:0px;" /></div>
		<a id="ctl00_RelatedLibrary_RelatedResults_ctl04_Link" class="title" href="/ResearchLibrary/40/Protecting-Your-Business-Data-Five-Do-s-and-Don-ts">Protecting Your Business Data: Five Do’s and Don’ts</a>
		
	</div>
	
	</div>
	

				</div>

				
				
			</div>
		</td>
		</tr></table>

		
		<div class="theme1-background" style="height:2px"></div>

		<div class="extended tiny-text">
			<div class="row">
				<div class="float-left">
					<a id="ctl00_PermaLink" itemprop="url" href="/Articles/5412/Writing-own-regular-expression-parser">Permalink</a> | 
					<a id="ctl00_AdvertiseLink" href="http://developermedia.com/">Advertise </a> |
					<a id="ctl00_PrivacyLink" href="/info/privacy.aspx">Privacy</a> |
					<a id="ctl00_Mobile" rel="nofollow" href="/Articles/5412/Writing-own-regular-expression-parser?display=Mobile">Mobile</a>
					<br />
								
					
					Web04 |
					2.8.140402.1 |
					Last Updated 15 Nov 2003								
				</div>
				<div class="float-right align-right">
					Article Copyright 2003 by Amer Gerzic<br />Everything else
					Copyright &copy; <a href="mailto:webmaster@codeproject.com">CodeProject</a>, 1999-2014 <br />
					<a id="ctl00_TermsOfUseLink" href="/info/TermsOfUse.aspx">Terms of Use</a>
				</div>

				


<div class="page-width">
Layout: <a id="ctl00_PageWidth_FixedT" title="Fixed width layout" rel="nofollow" class=" active" href="/Articles/5412/Writing-own-regular-expression-parser?PageFlow=FixedWidth">fixed</a>
|
<a id="ctl00_PageWidth_FluidT" title="Fluid layout" rel="nofollow" href="/Articles/5412/Writing-own-regular-expression-parser?PageFlow=Fluid">fluid</a>
</div>



			</div>
		</div>
		

		<br clear="all" />
		
			

	</div> 
	</div>
</div>


<div style="display:none;" id="dm_AdTable">
	
</div>




<script type="text/javascript" language="Javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.6.2/jquery.min.js"></script><script type='text/javascript'>//<![CDATA[
if (typeof jQuery == 'undefined') {
    document.write(unescape("%3Cscript src='/script/JS/jquery-1.6.2.min.js' type='text/javascript' %3E%3C/script%3E"));
}//]]></script>
<script type="text/javascript" language="Javascript" src="http://s.codeproject.com/script/Articles/JS/article.min.js?dt=2.8.140402.1"></script>
<script type="text/javascript" language="Javascript" src="http://s.codeproject.com/script/JS/navbar.min.js?dt=2.8.140402.1"></script>
<script type="text/javascript" language="Javascript" src="http://s.codeproject.com/script/Membership/JS/Notifications.min.js?dt=2.8.140402.1"></script>
<script type="text/javascript" language="Javascript">//<![CDATA[
$(document).ready(function() { anchorAnimate(); });
function markAllText(){
 markTextInElement('thompson','contentdiv');
 markTextInElement('nfa','contentdiv');
 markTextInElement('javascript','contentdiv');
}
$(function(){markAllText()});
(function(d, s, id) {  var js, fjs = d.getElementsByTagName(s)[0]; if (d.getElementById(id)) return; js = d.createElement(s); js.id = id; js.src = "//connect.facebook.net/en_GB/all.js#xfbml=1"; fjs.parentNode.insertBefore(js, fjs);}(document, 'script', 'facebook-jssdk'));
(function() {var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0];if(!d.getElementById(id)){ js=d.createElement(s);js.id=id; js.src="//platform.twitter.com/widgets.js";fjs.parentNode.insertBefore(js,fjs);}}(document,"script","twitter-wjs");
var DMReportsOK = null;function showDMAlert() {   var $div = $('div.msg-728x90');  $div.append($('<img src="/images/alert-top-block.gif" style="right:0;position:absolute;z-index:0">'));}function onDMcallBack(event){   if (event.originalEvent) event = event.originalEvent;   jQuery.support.cors = true;   if (event.data === 'DM:Disabled') DMReportsOK = false;   else if (event.data === 'DM:Enabled' || event.data=='DM-enabled') DMReportsOK = true;   else if (typeof event.data == 'object' && event.data.sender &&             event.data.sender == 'DeveloperMedia' && event.data.application=='apps' &&            event.data.action == 'reportEnabled') {            DMReportsOK = event.data.data.eanbled;   }}function checkLoaded() {  var recordCheck  = false; var showBlockMsg = false; var block        = 'None'; if (!DMReportsOK && block == 'None' && typeof DMAds === 'undefined')     block = 'ResourceBlocked'; if (DMReportsOK === true) block = 'None'; else if (DMReportsOK === false) block = 'DomModified'; if (recordCheck) {  $.ajax({ url:'/script/AdServe/Ajax/VS.aspx',data:{'adbm':block}, cache:false, async:true }); } if (showBlockMsg && block != 'None')    showDMAlert();}$(document).ready(function() {  $(window).bind('message', onDMcallBack);  setTimeout(checkLoaded, 4000);});
$(function ()
                {
                    $('.oauth').click(function () {
                        $this = $(this);
                        href = $this.attr('href');
                        var myWindow = window.open(href, 'popup',
                                    'width=800,height=600,location=0,menubar=0,resizeable=0,scrollbars=0,toolbar=0');
                        myWindow.focus();
                        var timer = setInterval(function () {
                                        if (myWindow.closed) {
                                            clearInterval(timer);
                                            // window.location.reload(); // May do a POST reload, shows a warning
                                            window.location = window.location; // force a GET reload
                                        }
                                    }, 200);
                        return false;
                    });
                });
var oSrchFlt = false, oSrchBox=false,srchBoxFoc=false;
$(document).ready(function() {
 if(InitWatermark)InitWatermark('sb_tb', 'Search for articles, questions, tips');
 var sbar = $('#sb_tb'); 
 var sfilter = $('#SearchFilter');
 if (sbar && sfilter) {
  sfilter.removeClass('popup'); sfilter.hide();
  sbar.blur(function() {
 if (!oSrchFlt)sfilter.hide();
 srchBoxFoc=false;
 /*sbar.animate( { width:'210px' }, { queue:false, duration:300 });
*/ });
  sbar.focus(function() {
 oSrchFlt=false;srchBoxFoc=true;
 sfilter.show();
 /*sbar.animate( { width:'500px' }, { queue:false, duration:300 });
*/ });
  sbar.mouseleave(function() { oSrchBox=false; });
  sbar.mouseover(function() { oSrchBox=true; });
  sfilter.mouseleave(function() { oSrchFlt=false; if (!srchBoxFoc&&!oSrchBox)sfilter.hide();});
  sfilter.mouseover(function() { oSrchFlt=true; });
 }
});
$('#clear-rate_ctl00_RateArticle_RSU').click(function () {    $('#ctl00_RateArticle_RSU').hide(); return false;});$("#ctl00_RateArticle_RateItemWrapper")   .removeClass("container-rating")   .hover( function() { $('#ctl00_RateArticle_RSU').fadeIn('fast'); },            function() { $('#ctl00_RateArticle_RSU').fadeOut('fast'); } );
function PostBack_ctl00_RateArticle_RateItemWrapper() {
  return rateItem(5412,2,1,true,true,3,'LargeStars');
}

                        function getVotesHistogram(objectId, objectTypeId, containerId, loadingId) {
                            if (!$('#' + containerId).attr('alreadyRequested')){
                                $.ajax({
                                    url: '/script/Ratings/Ajax/Histogram.aspx?obid=' + objectId + '&obtid='+objectTypeId,
                                    success: function (data) {
                                        $('#' + containerId).html(data);
                                        $('#' + loadingId).hide();
                                    }
                                });
                                $('#' + containerId).attr('alreadyRequested', 'true');
                            }
                        }
$(document).ready(function() {   new starRating('#ctl00_RateArticle_VoteFormDiv', PostBack_ctl00_RateArticle_RateItemWrapper,'ctl00_RateArticle');
  $('#ctl00_RateArticle_RB').mouseenter(function() {     getVotesHistogram(5412,2   ,'ctl00_RateArticle_Histogram','ctl00_RateArticle_Loading');  })})
$(document).ready(function() { $('#ctl00_RateArticle_SubmitRateBtn').hide(); });
$(document).ready(function() { $('#ctl00_RateArticle_SubmitRateBtn').hide(); });function ChkRtctl00_RateArticle(){}

forumDir = '/script/Forums/';
staticServer = 'http://s.codeproject.com';
allowReporting = false;
allowRating = false;
allowRatingDisplay = true;
var smoothScroll = true;
Selected        = -1;
oldTitle        = document.title;
minMessageScore = 1;
minMessageScore = 5;
abuseScore      = -2;
spamScore       = -1;
getRatingUrl    = '/script/Ratings/Ajax/GetRatings.aspx';
noiseThreshold  = 3;
getRatingRefKey = 'obrs';


//]]>
</script>


</body>
</html>